Homomorphisms are a good basis for counting small subgraphs

DOI10.1145/3055399.3055502MaRDI QIDQ4977973zbMATH OpenOpenAlexFDO

Authors Radu Curticapean, Holger Dell, Dániel Marx

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.01595, http://eprints.sztaki.hu/9230/

counting subgraphs exponential-time hypothesis fixed-parameter tractability homomorphisms

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

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'asz 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)} c d o t n^{0.174 k + o (k)}

by a surprisingly simple algorithm. This improves upon previously known running times, such as

O (n^{0.91 k + c})

time for

k

-edge matchings or

O (n^{0.46 k + c})

time for

k

-cycles. Furthermore, we prove a general complexity dichotomy for evaluating graph motif parameters: Given a class

m a t h c a l C

of such parameters, we consider the problem of evaluating

f i n m a t h c a l C

on input graphs

G

, parameterized by the number of induced subgraphs that

f

depends upon. For every recursively enumerable class

m a t h c a l 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

m a t h c a l 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.

Recommendations

Cited in

(74)

This page was built for publication: Homomorphisms are a good basis for counting small subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4977973)