Die Komplexität des dominierenden Mengenproblems in bestimmten Unterklassen von Akkordgraphen

Ich interessiere mich für die Komplexität des Dominating-Set-Problems (DSP) in einigen spezifischen Graphenklassen, die Unterklassen von Akkordgraphen sind .

Ein Diagramm ist ein ungerichtetes Pfaddiagramm, wenn es sich um das Scheitelpunkt-Schnittdiagramm einer Pfadfamilie in einem ungerichteten Baum handelt. Sei UP die Klasse der ungerichteten Pfadgraphen.

Ein Diagramm ist ein EPT-Diagramm, wenn es sich um das Kantenschnittdiagramm einer Pfadfamilie in einem ungerichteten Baum handelt. Ein EPT-Diagramm ist möglicherweise nicht akkordisch, aber CEPT ist die Klasse der akkordischen EPT-Diagramme.

Ein Graph ist ein (verwurzelter) gerichteter Pfadgraph, wenn es sich um den Scheitelpunkt-Schnittpunkt-Graphen einer Familie gerichteter Pfade in einem verwurzelten gerichteten Baum handelt (dh alle von der Wurzel weggerichteten Bögen). Sei RDP die Klasse der (verwurzelten) gerichteten Pfadgraphen.

Wir haben$RDP\subseteq CEPT \subseteq UP\subseteq chordal$

Es ist bekannt, dass der DSP für Graphen in RDP linear zeitlich lösbar ist, für Graphen von UP jedoch NP-vollständig ist [ Booth and Johnson, 1981 ].

Ich interessiere mich für spezielle Graphen, die Scheitelpunkt-Schnitt-Graphen von Familien ungerichteter Pfade in raupenähnlichen Bäumen des maximalen Grades 3 entsprechen. Genauer gesagt, diese "Raupen" sind aus einem Pfad aufgebaut, in dem jeder zweite Scheitelpunkt einen hängenden Grad hat. Ein-Eckpunkt angehängt an. Nennen wir diese Klasse cat-up.

Darüber hinaus können meine speziellen Graphen auch als Kantenschnittgraphen einiger Familien ungerichteter Pfade in bestimmten Bäumen mit maximalem Grad 3 konstruiert werden.

Meine Fragen sind also:

1) Ist die Komplexität des DSP für Cat-UP-Diagramme bekannt? (Beachten Sie, dass die Reduktion in [ Booth and Johnson, 1981 ] einen Wirtsbaum mit maximalem Grad 3 erzeugt, der jedoch weit von einer Raupe entfernt ist.)

2) Wie komplex ist DSP für CEPT-Diagramme? Und für Diagramme der CEPT entsteht ein Wirtsbaum mit maximalem Grad 3? ( dies ist ISGCI nicht bekannt )

3) Gibt es ein Komplexitätsergebnis für den DSP in einer eng verwandten Graphenfamilie?

Schade, dass Sie so lange gewartet haben, ohne eine Antwort zu bekommen. Ich weiß nicht, für welche Klassen Sie sich entschieden haben, aber ich kenne einige verwandte Grafikklassen und neue Techniken, die Sie ausprobieren können.

Zuerst möchte ich erwähnen, dass Steven Chaplick Arbeiten an verwandten Grafikklassen durchgeführt hat. Er hat seine Doktorarbeit Anfang dieses Jahres abgeschlossen. Vielleicht finden Sie seine Forschung interessant.

Ich weiß, dass einige Ergebnisse in dieser Richtung aus meiner eigenen Arbeit stammen. Graph Classes with Structured Neighborhoods and Algorithmic Applications ( Graphenklassen mit strukturierten Nachbarschaften und algorithmischen Anwendungen) Dies gibt eine allgemeine Technik zum Lösen verschiedener Probleme, einschließlich DSP in bestimmten Graphenklassen. Wir tun dies, indem wir neue Graphenzerlegungen einführen (siehe meine These ).

$(d-1)^{3(s-1)}poly(n)$

$0$$k \times n$

Die gleiche Technik könnte für die CEPT funktionieren, die aus einem Wirtsbaum mit maximalem Grad 3 hervorgeht, aber ich brauche etwas mehr Zeit, um diese Klasse zu verstehen. Wenn Sie einen Link zu einigen Charakterisierungen dieser Klasse haben, würde das helfen.