Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)

DOI10.4230/LIPICS.STACS.2014.542MaRDI QIDQ2965515zbMATH OpenOpenAlexFDO

Authors Dániel Marx, Michał Pilipczuk

Publication date 3 March 2017

Full work available at URL https://arxiv.org/abs/1307.2187

zbMATH Keywords

parameterized complexitysubgraph isomorphism

Mathematics Subject Classification ID

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

Abstract: Given two graphs $H$ and $G$, the Subgraph Isomorphism problem asks if $H$ is isomorphic to a subgraph of $G$. While NP-hard in general, algorithms exist for various parameterized versions of the problem: for example, the problem can be solved (1) in time $2^{O(|V(H)|)}cdot{n}^{O(w(H))}$ using the color-coding technique of Alon, Yuster, and Zwick; (2) in time $f(|V(H)|,w(G))cdotn$ using Courcelle's Theorem; (3) in time $f(|V(H)|,genus(G))cdotn$ using a result on first-order model checking by Frick and Grohe; or (4) in time $f(maxdeg(H))cdot{n}^{O(w(G)})$ for connected $H$ using the algorithm of Matouv{s}ek and Thomas. Already this small sample of results shows that the way an algorithm can depend on the parameters is highly nontrivial and subtle. We develop a framework involving 10 relevant parameters for each of $H$ and $G$ (such as treewidth, pathwidth, genus, maximum degree, number of vertices, number of components, etc.), and ask if an algorithm with running time [ f_1(p_1,p_2,..., p_ell)cdot n^{f_2(p_{ell+1},..., p_k)} ] exist, where each of $p_1,\mathrm{...},p_k$ is one of the 10 parameters depending only on $H$ or $G$. We show that {em all} the questions arising in this framework are answered by a set of 11 maximal positive results (algorithms) and a set of 17 maximal negative results (hardness proofs); some of these results already appear in the literature, while others are new in this paper. On the algorithmic side, our study reveals for example that an unexpected combination of bounded degree, genus, and feedback vertex set number of $G$ gives rise to a highly nontrivial algorithm for Subgraph Isomorphism. On the hardness side, we present W[1]-hardness proofs under extremely restricted conditions, such as when $H$ is a bounded-degree tree of constant pathwidth and $G$ is a planar graph of bounded pathwidth.

Recommendations

• Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width
• Faster algorithms for finding and counting subgraphs
• The complexity of subgraph isomorphism for classes of partial k-trees
• Subgraph isomorphism on graph classes that exclude a substructure
• Understanding the Complexity of Induced Subgraph Isomorphisms

Cited in

(25)

• scientific article; zbMATH DE number 7559154 (Why is no real title available?)
• scientific article; zbMATH DE number 7559382 (Why is no real title available?)
• Grundy Distinguishes Treewidth from Pathwidth
• On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
• Finding a chain graph in a bipartite permutation graph
• scientific article; zbMATH DE number 7650232 (Why is no real title available?)
• Envy-free allocations respecting social networks
• A multiparametric view on answer set programming
• Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
• Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width
• Mine 'em all: a note on mining all graphs
• Rural postman parameterized by the number of components of required edges
• Almost tight lower bounds for hard cutting problems in embedded graphs
• Improved hardness of maximum common subgraph problems on labeled graphs of bounded treewidth and bounded degree
• On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
• Beating treewidth for average-case subgraph isomorphism
• A Tight Algorithm for Strongly Connected Steiner Subgraph on Two Terminals with Demands (Extended Abstract)
• Probabilistic and exact frequent subtree mining in graphs beyond forests
• Monotone arithmetic complexity of graph homomorphism polynomials
• Grundy distinguishes treewidth from pathwidth
• Understanding the Complexity of Induced Subgraph Isomorphisms
• Subgraph isomorphism on graph classes that exclude a substructure
• On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
• A tight lower bound for planar Steiner orientation
• A tight algorithm for strongly connected Steiner subgraph on two terminals with demands

This page was built for publication: Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)

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