2008 | OriginalPaper | Buchkapitel
Understanding the Complexity of Induced Subgraph Isomorphisms
verfasst von : Yijia Chen, Marc Thurley, Mark Weyer
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study left-hand side restrictions of the
induced subgraph isomorphism
problem: Fixing a class
, for given graphs
G
and arbitrary
H
we ask for induced subgraphs of
H
isomorphic to
G
.
For the homomorphism problem this kind of restriction has been studied by Grohe and Dalmau, Kolaitis and Vardi for the decision problem and by Dalmau and Jonsson for its counting variant.
We give a dichotomy result for both variants of the induced subgraph isomorphism problem. Under some assumption from parameterized complexity theory, these problems are solvable in polynomial time if and only if
contains no arbitrarily large graphs.
All classifications are given by means of parameterized complexity. The results are presented for arbitrary structures of bounded arity which implies, for example, analogous results for directed graphs.
Furthermore, we show that no such dichotomy is possible in the sense of classical complexity. That is, if
there are classes
such that the induced subgraph isomorphism problem on
is neither in
nor
-complete. This argument may be of independent interest, because it is applicable to various parameterized problems.