Name
Abstract | ||
|---|---|---|
We introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lovász show that many interesting quantities have this form, including, for fixed graphs H, the number of H-copies (induced or not) in an input graph G, and the number of homomorphisms from H to G. We use the framework of graph motif parameters to obtain faster algorithms for counting subgraph copies of fixed graphs H in host graphs G. More precisely, for graphs H on k edges, we show how to count subgraph copies of H in time kO(k)· n0.174k + o(k) by a surprisingly simple algorithm. This improves upon previously known running times, such as O(n0.91k + c) time for k-edge matchings or O(n0.46k + c) time for k-cycles. Furthermore, we prove a general complexity dichotomy for evaluating graph motif parameters: Given a class C of such parameters, we consider the problem of evaluating fâ C on input graphs G, parameterized by the number of induced subgraphs that f depends upon. For every recursively enumerable class C, we prove the above problem to be either FPT or #W[1]-hard, with an explicit dichotomy criterion. This allows us to recover known dichotomies for counting subgraphs, induced subgraphs, and homomorphisms in a uniform and simplified way, together with improved lower bounds. Finally, we extend graph motif parameters to colored subgraphs and prove a complexity trichotomy: For vertex-colored graphs H and G, where H is from a fixed class of graphs, we want to count color-preserving H-copies in G. We show that this problem is either polynomial-time solvable or FPT or #W[1]-hard, and that the FPT cases indeed need FPT time under reasonable assumptions. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1145/3055399.3055502 | STOC |
Keywords | DocType | Volume |
counting subgraphs,homomorphisms,fixed-parameter tractability,exponential time hypothesis | Conference | abs/1705.01595 |
ISSN | Citations | PageRank |
0737-8017 | 8 | 0.54 |
References | Authors | |
35 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Radu Curticapean | 1 | 70 | 8.75 |
| Holger Dell | 2 | 220 | 16.74 |
| Dániel Marx | 3 | 1952 | 113.07 |