PaperlayerView exact revision on arXiv

Source-linked AI summary

Homomorphisms Are a Good Basis for Counting Small Subgraphs

Radu Curticapean, Holger Dell, Dániel Marx

arXiv:1705.01595v1cs.DScs.CCcs.DM

TL;DR

The paper addresses counting subgraph occurrences, which can be harder than deciding whether they exist. It uses graph motif parameters and homomorphism-based transformations to obtain faster counting algorithms and complexity classifications.

  • Problem

    Counting subgraph occurrences can be substantially harder than deciding whether a pattern exists, as shown by the contrast between polynomial-time perfect-matching existence and #P-hard counting.

  • Method

    The paper unifies subgraph-counting methods through graph motif parameters and rewrites relevant quantities as linear combinations of homomorphism numbers.

  • Results

    For a k-edge pattern H and an n-vertex graph G, subgraph counts can be computed in time k^O(k) · n^0.174·k+o(k), while related counting problems admit dichotomy results based on treewidth.

  • Takeaways & Limitations

    The framework provides a unified basis for faster subgraph counting and for recovering complexity classifications across related graph-counting problems.

  • Takeaways & Limitations

    The decision version of the subgraph-counting dichotomy remains open beyond hereditary graph classes.

Abstract

from arXiv · show

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$. Using the framework of graph motif parameters, we obtain faster algorithms for counting subgraph copies of fixed graphs $H$ in host graphs $G$: For graphs $H$ on $k$ edges, we show how to count subgraph copies of $H$ in time $k^{O(k)}\cdot n^{0.174k + o(k)}$ by a surprisingly simple algorithm. This improves upon previously known running times, such as $O(n^{0.91k + c})$ time for $k$-edge matchings or $O(n^{0.46k + c})$ time for $k$-cycles. Furthermore, we prove a general complexity dichotomy for evaluating graph motif parameters: Given a class $\mathcal C$ of such parameters, we consider the problem of evaluating $f\in \mathcal C$ on input graphs $G$, parameterized by the number of induced subgraphs that $f$ depends upon. For every recursively enumerable class $\mathcal 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 $\mathcal H$, 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.

1 Introduction

The paper develops a homomorphism-based framework for counting small subgraphs and graph motif parameters, yielding faster algorithms and broad complexity classifications. It also unifies subgraph, induced-subgraph, homomorphism, and colored-pattern counting through basis transformations.

  • Motivation: Counting subgraph copies is harder than deciding existence, motivating algorithms for small patterns in large host graphs.Counting perfect matchings is #P-hard although perfect-matching existence is polynomial-time decidable.
  • Subgraph counting: Theorem 1.1 counts a k-edge pattern H in time k^{O(k)} · n^{t+1}, where t is the maximum treewidth among graphs in H's spasm.The spasm contains homomorphic images obtained by merging non-adjacent vertices.
  • Subgraph counting: O(n^3) counts 4-paths and 6-paths because every graph in their spasm has treewidth at most two.More generally, patterns whose spasm has treewidth at most two admit an f(H) · |V(G)|^ω algorithm.
  • Subgraph counting: 0.174k + o(k) is the exponent in the paper's general bound for counting k-edge subgraphs, improving prior 0.91k and 0.455k exponents for matchings and paths.The algorithm is also described as significantly simpler than the previous approach.
  • Complexity classifications: Theorem 1.5 gives a dichotomy for subgraph counting: bounded vertex-cover classes are polynomial-time solvable, otherwise they are #W[1]-complete parameterized by pattern size.Under #ETH, hard recursively enumerable classes also cannot be solved in f(H) · n^{o(vc(H)/log vc(H))} time.
  • Limitations: The paper identifies a limitation in the surrounding theory: the decision analogue of the subgraph-counting dichotomy remains open beyond hereditary graph classes.Some non-hereditary cases have only recently been resolved.
  • Complexity classifications: Counting homomorphisms is polynomial-time solvable for bounded-treewidth classes and #W[1]-complete otherwise, with #ETH lower bounds for unbounded treewidth.The framework also yields fixed-parameter or #W[1]-hard classifications for induced-subgraph properties.
  • Unified framework: Graph motif parameters are finite linear combinations of induced-subgraph counts, and their complexity is governed by the nonzero homomorphism terms in an equivalent representation.This framework recovers dichotomies for subgraphs, induced subgraphs, and homomorphisms, while allowing cancellation to make apparently difficult combinations easier.

2 Preliminaries

The preliminaries define the graph, subgraph, homomorphism, coloring, treewidth, and parameterized-complexity notions used throughout. They also state the counting hardness assumptions underlying later lower bounds.

  • Parameterized complexity: A parameterized counting problem is FPT when it runs in f(k)·poly(n) time, whereas #W[1]-hardness is defined through parameterized reductions from counting k-cliques.
  • Graphs are finite, labeled, undirected, and simple, so they contain neither loops nor parallel edges.
  • A subgraph selects vertices and edges from G, while an induced subgraph additionally preserves all nonedges among its selected vertices.
  • A homomorphism maps vertices of H to vertices of G while sending every edge of H to an edge of G; embeddings additionally require injectivity.
  • Vertex-colored graphs assign each vertex a color, and a colorful subgraph contains exactly one vertex from every color class.
  • Treewidth: Treewidth is the minimum width of a tree decomposition, whose bags cover every vertex continuously and contain both endpoints of every edge.

3 The space of graph motif parameters

Graph motif parameters are finite linear combinations of induced-subgraph counts, and subgraph and homomorphism counts form equivalent bases for this space. Basis transformations connect these representations and expose algorithmic complexity through the homomorphism basis and graph spasms.

  • Definition: Graph motif parameters are graph parameters expressible as finite linear combinations of induced-subgraph numbers.They form the finitely supported row-span of the IndSub matrix.
  • Basis transformations: Subgraph, induced-subgraph, and homomorphism numbers span the same vector space of graph motif parameters.The paper uses basis transformations to move between these representations.
  • Subgraphs: Every fixed graph H yields a graph motif parameter Sub(H, ⋆) because H has only finitely many extensions.Subgraph counts are obtained as finite linear combinations of induced-subgraph counts over extensions of H.
  • Homomorphisms: The homomorphism basis is invertible on suitable finite graph sets because Surj is lower triangular with nonzero diagonal entries Aut(F).Its inverse expresses subgraph parameters as linear combinations of homomorphism counts.
  • Spasms: The nonzero entries of Surj^-1 identify exactly the graphs in Spasm(H), linking basis support to hardness arguments.A finite surjective-homomorphism-closed set yields an invertible principal Hom matrix.
  • Complexity: A homomorphism-basis combination can be evaluated in time g(α) + poly(|α|) · |V(G)|^(tw(α)+1), while unbounded treewidth yields #W[1]-hardness.Under #ETH, the hardness result rules out algorithms with exponent below tw(α)/log tw(α) up to parameter-dependent factors.

4 Algorithms for counting subgraphs

The paper counts subgraphs by transforming them into homomorphism counts over the spasm of the pattern, where the maximum spasm treewidth determines the host-graph exponent. This yields general bounds and faster special cases using matrix multiplication.

  • General algorithm: The homomorphism-basis reduction makes the maximum treewidth in Spasm(H) the governing exponent for subgraph counting.For fixed H, homomorphism counts for all spasm graphs suffice to recover Sub(H, G).
  • General algorithm: #Sub(H →G) can be computed in time k^O(k) · n^(t+1), where t is the maximum treewidth among graphs in Spasm(H).The algorithm computes the spasm and basis coefficients, then counts homomorphisms from each spasm graph.
  • Sparse patterns: The treewidth constant for k-edge graphs satisfies 1/36 ≤ ξ ≤ 13/75, giving ξ < 0.174.This implies an n^(ξk+o(k)) dependence for counting k-edge subgraphs.
  • Sparse patterns: The resulting bound for k-edge patterns is f(H) · |V(G)|^(ξk+o(k)).Here ξ is the limsup-based constant defined from the maximum treewidth of k-edge graphs.
  • Treewidth at most two: For patterns whose spasm has treewidth at most 2, fast matrix multiplication gives homomorphism counting in poly(|V(H)|) · |V(G)|^ω time.The method replaces the basic homomorphism-counting subroutine in the subgraph algorithm.
  • Treewidth at most two: The dynamic program stores two-vertex boundary tables and combines independent child-cone contributions using matrix multiplication.Naively evaluating each bag costs roughly |V(G)|^3, motivating the matrix formulation.

5 Complexity of linear combination problems

Complexity of linear combinations is determined by the treewidth of their homomorphism-basis support after the appropriate basis transformation. This yields dichotomies and lower bounds for subgraph and induced-subgraph counting, including hardness for broad pattern families.

  • Subgraph combinations: The relevant transformation for subgraph combinations is α · Surj^-1, which represents α · Sub in the homomorphism basis.The most difficult homomorphism term governs the complexity.
  • Pattern families: For a graph H with maximum matching size k, the maximum treewidth in Spasm(H) is Θ(k).The upper bound follows from vertex-cover relations, while the lower bound uses k-edge graphs with linear treewidth.
  • Subgraph combinations: Linear combinations of subgraph counts are tractable when their transformed homomorphism-basis supports have bounded treewidth, and otherwise are #W[1]-hard.The hard cases also exclude g(α) · n^o(t/log t) algorithms unless #ETH fails.
  • Pattern families: Counting all k-vertex trees is #W[1]-hard when parameterized by k.The result follows because the union of the spasms of k-vertex trees has unbounded treewidth.
  • Induced subgraphs: The induced-subgraph dichotomy uses the combined transformation α · Ext^-1 · Surj^-1.Bounded transformed treewidth gives an algorithm with exponent t+1; otherwise the problem is #W[1]-hard.
  • Graph properties: For any decidable graph property Φ, counting induced k-vertex subgraphs satisfying Φ is FPT exactly when the corresponding quantities have bounded-treewidth homomorphism representations; otherwise it is #W[1]-hard.This follows by expressing the property count as a sum of induced-subgraph numbers.

6 Counting colored subgraphs in polynomial time

This section characterizes when counting colored subgraphs is polynomial-time solvable by structural properties of the colored pattern and presents an algorithmic decomposition theorem. It also identifies half-colorful matchings as the obstruction underlying conditional hardness.

  • Polynomial-time solvability: The section studies which classes of vertex-colored graphs make #Sub(H) polynomial-time solvable beyond the known FPT criterion based on bounded-treewidth graphs in Spasm(H).The FPT criterion alone does not distinguish its polynomial-time cases.
  • Structural characterization: The same condition is equivalent to the existence of guarded cutvertex decompositions with bounded guard size and boundedly many colors per bag.Each guard is a vertex cover of the induced bag, and each child separator has at most one vertex outside the guard.
  • Structural characterization: Bounded treewidth of Spasm(H) is equivalent to bounded treewidth of bH together with the absence of arbitrarily large flowers centered at color classes.Here bH consolidates each color class into one vertex, while a c-flower is a vertex-disjoint collection of paths in H•\i with endpoints in one color class.
  • Algorithmic decomposition: Given bH treewidth at most w and no c-flower centered at any color class, a guarded decomposition can be computed with guard size O((w + c)^2w^2) and O((c + w)^w) colors per bag.This provides the algorithmic form needed for polynomial-time algorithms, rather than only an existence characterization.
  • Counting algorithm and hardness: For a tight guarded decomposition with guard size at most c, at most c colors per bag, and |λ(t)| ≤ d, Emb(H →G) can be computed in time 2^O(d) · |V (G)|^2O(c).Large λ(t) yields a large half-colorful matching, which supports reductions from counting perfect matchings.

6.1 Obtaining a tree decomposition

This section constructs guarded cutvertex decompositions from tree decompositions of H• under bounded treewidth and no-large-flower assumptions. The resulting decomposition has bounded guards and boundedly many colors per bag, enabling the polynomial-time counting algorithm.

  • Decomposition structure: Any guarded cutvertex decomposition with guard size at most c implies that H has treewidth at most c.The proof replaces each original bag by a guard bag and one-vertex extensions.
  • Decomposition structure: The decomposition rules out matchings of size c+1 within one color class or between any two color classes.This structural restriction is consistent with the role of large matchings as sources of counting hardness.
  • Constructing the decomposition: The constructed guards are vertex covers of the bag-induced graphs, and each component below a bag has at most one neighborhood vertex outside the guard.These properties provide the guarded cutvertex conditions used by the counting algorithm.

6.2 Half-colorful matchings

This section explains why certain FPT cases are not polynomial-time solvable: large λ(t) values create half-colorful matchings, which can encode perfect-matching counting.

  • Extracting matchings: If λ(t) has size at least k at some decomposition node, then H contains a half-colorful matching of size k/c^2 − 1.The matching is centered at one color class and uses distinct neighboring color classes.
  • Extracting matchings: The extraction follows because vertices in λ(t) come from at most c colors, while each color can occur at most c times among their matched neighbors.Selecting one color class with at least k/c vertices and filtering repeated neighbor colors gives the bound.
  • Cleaning matchings: When no large flowers exist, a half-colorful matching can be cleaned by discarding at most 3c edges, leaving vertices with unique neighboring color classes outside a small exceptional set.The cleaned structure has an exceptional set S of size at most 3c.
  • Hardness consequence: A cleaned half-colorful matching supports a reduction from counting perfect matchings in a bipartite graph to colored subgraph counting using oracle access to Sub(H →⋆).The reduction constructs a graph HG whose H-copies correspond exactly to perfect matchings after inclusion-exclusion constraints.
  • Hardness consequence: The reduction is described under simplifying assumptions excluding extra color classes, certain edges, and isolated vertices, with an extension to the general case stated as straightforward.The oracle reduction runs in time f(c)|V (H)|^O(1).

6.3 Algorithm

The algorithm counts embeddings through two nested dynamic programs over a guarded decomposition. Similar vertices are grouped into ordered partition classes, while inner states control partial mappings and branch attachments.

  • Ordering and similarity: Vertices are partitioned according to similarity, meaning equal colors and equal open neighborhoods, and the algorithm counts partition-ordered embeddings.Every ordinary embedding can be recovered by permuting images within similarity classes.
  • Inner dynamic programming: Π-prefix states are valid because the vertices mapped to host vertices at most i form a prefix within every similarity class.This permits incremental processing of host vertices while preserving ordered embeddings.
  • Outer dynamic programming: The outer dynamic program processes decomposition nodes bottom-up and stores counts indexed by embeddings of the separator σ(t).It refines these states by fixing the embedding on the larger guard g(t).
  • Inner dynamic programming: The inner dynamic program increases an index i that restricts non-guard bag vertices to the first i host vertices.Its states also record a Π-prefix subset S and a fixed guard mapping f.
  • Inner dynamic programming: When a λ(t) vertex is inserted, the algorithm combines its mapping with already computed child states whose separators attach through that vertex.The guarded condition ensures these child attachments depend only on the guard mapping and the new host vertex.

6.4 Putting it together

The section classifies when counting colored subgraph patterns is polynomial-time solvable, under a bounded-treewidth condition on their spasm graphs. Polynomial time is characterized by logarithmic growth of the largest half-colorful matching; otherwise it is conditionally not polynomial-time solvable.

  • Under the theorem’s assumption, every graph in Spasm(H) has treewidth at most a fixed constant c.
  • If the largest half-colorful matching is at most h log |V(H)| for a constant h, then #Sub(H) is polynomial-time solvable.The proof obtains bounded-treewidth decompositions with bounded guard size and bounded colors per bag.
  • Otherwise, #Sub(H) is not polynomial-time solvable unless the Nonuniform Counting Exponential Time Hypothesis fails.The negative direction uses infinitely many patterns whose largest half-colorful matching grows at least logarithmically with pattern size.

7 Open Problems

The paper identifies further questions about computationally useful bases and subspaces beyond the three established bases of graph motif parameters. These open problems concern whether other bases or parameter spaces yield similarly useful structure.

  • The framework uses Hom, Sub, and IndSub as three useful bases for graph motif parameters.Basis changes transfer results between the corresponding counting-problem classes.
  • Open questions ask whether other computationally interesting bases exist and whether other interesting subspaces lie outside graph motif parameters.

A Appendix

The appendix supplies omitted proofs and supporting reductions for colored subgraph counting, homomorphism lower bounds, and treewidth-based dynamic programming. Its arguments use inclusion–exclusion for color-preserving copies and standard tree-decomposition tables for homomorphism counting.

  • The appendix contains proofs omitted from the main text.
  • Treewidth dynamic programming: The homomorphism dynamic program stores, for each tree-decomposition bag mapping, the number of extensions over the vertices below that bag.Leaf, introduce, forget, and join nodes update these tables using initialization, restriction, neighborhood intersections, and multiplication, respectively.
  • Treewidth dynamic programming: Forget-node processing runs in ˜O(tw(H) · |V(G)|^(tw(H)+1)) time by intersecting host-graph neighborhoods.Join-node updates multiply matching table entries, while introduce nodes copy restricted entries.
  • Colored subgraph counting: PartitionedSub(F) counts vertex-colorful copies and has treewidth as its tractability criterion, with near-tight lower bounds under #ETH.
  • Homomorphism lower bound: For recursively enumerable graph classes of unbounded treewidth, #Hom(F) has no f(H) · |V(G)|^o(tw(H)/ log tw(H)) algorithm if #ETH holds.
  • Colored subgraph counting: A vertex-colorful reduction counts color-preserving H-copies by combining homomorphism counts after deleting color classes.Inclusion–exclusion isolates homomorphisms that map each pattern vertex to its matching color, and division by #Aut(H) yields vertex-colorful copies.
Loading 1705.01595v1…