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

DOI10.4230/LIPICS.STACS.2014.542zbMATH Open1359.68139arXiv1307.2187OpenAlexW2962884946MaRDI QIDQ2965515FDOQ2965515

Authors: Dániel Marx, Michał Pilipczuk 

Publication date: 3 March 2017

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.

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

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

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)

Cited In (25)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Grundy Distinguishes Treewidth from Pathwidth
• On the complexity of computing the \(k\)-restricted edge-connectivity of a graph
• Title not available (Why is that?)
• Finding a chain graph in a bipartite permutation graph
• Envy-free allocations respecting social networks
• A multiparametric view on answer set programming
• Characterizing the complexity of subgraph isomorphism for graphs of bounded path-width
• Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
• Mine 'em all: a note on mining all graphs
• Almost tight lower bounds for hard cutting problems in embedded graphs
• Rural postman parameterized by the number of components of required edges
• 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)