Subgraph-Isomorphie mit einem Baum

Wenn wir einen großen (gerichteten) Graphen und einen kleineren Stammbaum , welche Komplexität ist am bekanntesten, um zu isomorphe Untergraphen von zu finden ? Mir sind Ergebnisse für Teilbaumisomorphien bekannt, bei denen sowohl als auch Bäume sind und bei denen eben ist oder eine begrenzte Baumbreite (und andere) aufweist, jedoch nicht für diesen Diagramm- und Baumfall. $G$ $H$ $G$ $H$ $G$ $H$ $G$

ds.algorithms reference-request graph-theory Raphael
quelle

Meinen Sie damit induzierten Subgraphen anstelle von Subgraphen?

Kristoffer Arnsfelt Hansen

@Kristoffer, mich interessieren beide. Habe ich etwas Triviales an dem nicht induzierten Fall verpasst?

Raphael

Ihr Problem ist NP-hart, auch wenn

H

$H$ ein Pfad ist, da das längste (induzierte oder nicht induzierte) Pfadproblem NP-hart ist.

Yota Otachi

Ja. Ich interessiere mich für das, was mehr darüber bekannt ist, dass

ein Baum ist. Zum Beispiel, abhängig von Eigenschaften von

wie die in der Frage oder angenommen,

ist festgelegt usw.

H

$H$

G

$G$

H

$H$

Raphael

Das induzierte Pfadproblem ist W [1] -vollständig (Papadimitriou-Yannakakis 1991), während das (nicht induzierte) Pfadproblem FPT ist (Monien 1985). Siehe auch Chen-Flum 2007. Ich möchte auch die parametrisierte Komplexität für andere Baumklassen kennen.

Yota Otachi

Antworten:

Die Frage, ob irgendein fester Graph ein (induzierter) Teilgraph von ist, ist eine definierbare Eigenschaft erster Ordnung, dh für jedes gibt es eine Formel ( ), so dass ein (induzierter) Teilgraph von if ist und nur dann , wenn ( ). $H$ $G$ $H$ $\varphi_H$ $\psi_H$ $H$ $G$ $G \models \varphi_H$ $G\models\psi_H$

Früher war bekannt, dass das Modellprüfungsproblem für Klassen von Diagrammen, die (lokal) eine untergeordnete Erweiterung ausschließen, und für Klassen mit (lokal) begrenzter Erweiterung über festgelegte Parameter verfolgbar ist . Kürzlich kündigten Grohe, Kreutzer und S. ein noch allgemeineres Meta-Theorem an, das besagt, dass jede Eigenschaft erster Ordnung in nahezu linearer Zeit auf nirgendwo dichten Klassen von Graphen entschieden werden kann.

Für Ihre Frage bedeutet dies Folgendes. Sei ein fest verwurzelter Baum. Dann kann in linearer Zeit entschieden werden, ob ein (induzierter) Teilgraph eines eingegebenen (gerichteten oder ungerichteten) Graphen wenn planar ist, oder allgemeiner aus einer Klasse stammt, die einen Nebengraphen ausschließt, oder aus einer Klasse begrenzter Expansion. Das Problem kann in nahezu linearer Zeit entschieden werden, wenn aus einer Klasse stammt, die lokal ein Moll oder eine Klasse lokal begrenzter Expansion ausschließt, oder im Allgemeinen aus einer nirgendwo dichten Klasse von Graphen stammt. $H$ $H$ $G$ $G$ $G$ $G$

Sebastian Siebertz
quelle

Es kann in randomisierten erwartete Zeit gelöst werden , wo die Größe des kleinen gerichteten Baums zu finden ist , und ist die Anzahl der Kanten des großen gerichteten Graphen , in denen sie zu finden. Siehe Satz 6.1 von Alon, N., Yuster, R. und Zwick, U. (1995). Farbcodierung. J. ACM 42 (4): 844–856 . Alon et al. Geben Sie außerdem an, dass der Algorithmus derandomisiert werden kann, geben Sie jedoch nicht die Details für diesen Teil an. Ich denke, die deterministische Zeit könnte etwas größer sein, eher wie $O(2^km)$ $k$ $m$ . $O(k!\,m)$

David Eppstein
quelle

Die derandomisierte Version sollte wie gewohnt sein, z. B. wie in Abschnitt 4 beschrieben, und nur die perfekte Hash-Funktion verwenden, um

Knoten auf

Farbe abzubilden , was zu einem zusätzlichen

-Faktor führt. (kann auch verbessert werden

Faktor, Mitteln vollständig ist

n

$n$

k

$k$

\log^{2} n

$\log^2 n$

\log n

$\log n$

O (2^{k} \cdot m \cdot \log n)

$O(2^k \cdot m \cdot \log n)$

Saeed

$H$

Radu Curticapean
quelle