Name
Abstract | ||
|---|---|---|
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(k2). 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1145/2786017 | TOCT |
Keywords | Field | DocType |
Counting complexity,parameterized complexity,Ramsey theory | Ramsey theory,Discrete mathematics,Graph,Combinatorics,Parameterized complexity,Vertex (geometry),Counting problem,Mathematics,Special case | Journal |
Volume | Issue | ISSN |
7 | 3 | 1942-3454 |
Citations | PageRank | References |
4 | 0.41 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| mark jerrum | 1 | 2755 | 564.62 |
| Kitty Meeks | 2 | 44 | 8.20 |