License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.542
URN: urn:nbn:de:0030-drops-44863
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4486/
Marx, Dániel ;
Pilipczuk, Michal
Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)
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. However, the literature contains very little guidance on which combinations of parameters can or cannot be exploited algorithmically. Our goal is to systematically investigate the possible parameterized algorithms that can exist for Subgraph Isomorphism.
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 f1_(p_1,p_2,...,p_l).n^f_2(p_(l+1),...,p_k) exists, where each of p_1,...,p_k is one of the 10 parameters depending only on H or G. We show that 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.
BibTeX - Entry
@InProceedings{marx_et_al:LIPIcs:2014:4486,
author = {D{\'a}niel Marx and Michal Pilipczuk},
title = {{Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask)}},
booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
pages = {542--553},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-65-1},
ISSN = {1868-8969},
year = {2014},
volume = {25},
editor = {Ernst W. Mayr and Natacha Portier},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4486},
URN = {urn:nbn:de:0030-drops-44863},
doi = {10.4230/LIPIcs.STACS.2014.542},
annote = {Keywords: parameterized complexity, subgraph isomorphism}
}
|
Keywords: |
|
parameterized complexity, subgraph isomorphism |
|
Collection: |
|
31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) |
|
Issue Date: |
|
2014 |
|
Date of publication: |
|
05.03.2014 |
