Details

Autor(en) / Beteiligte

• Jerrum, Mark
• Meeks, Kitty

Titel

Some Hard Families of Parameterized Counting Problems

Ist Teil von

• ACM transactions on computation theory, 2015-07, Vol.7 (3), p.1-18

Erscheinungsjahr

2015

Link zum Volltext

Quelle

ACM Digital Library

Beschreibungen/Notizen

• We consider parameterized subgraph counting problems of the following form: given a graph G , how many k -tuples of its vertices induce a subgraph with a given property? A number of such problems are known to be #W[1]-complete; here, we substantially generalize some of these existing results by proving hardness for two large families of such problems. We demonstrate that it is #W[1]-hard to count the number of k -vertex subgraphs having any property where the number of distinct edge densities of labeled subgraphs that satisfy the property is o ( k 2 ). In the special case in which the property in question depends only on the number of edges in the subgraph, we give a strengthening of this result, which leads to our second family of hard problems.