Unterteilen kubischer Diagramme in Klauen und Pfade

Wieder ein Edge-Partitioning-Problem, auf dessen Komplexität ich neugierig bin, motiviert durch eine frühere Frage von mir .

Eingabe: ein kubischer Graph $G=(V,E)$

Frage: Gibt es eine Aufteilung von in E 1 , E 2 , ... , E s , so dass der von jedem E i induzierte Teilgraph entweder eine Klaue (dh K 1 , 3 , oft als Stern bezeichnet) oder ein 3- Pfad ist (dh P 4 )?$E$$E_1, E_2, \ldots, E_s$$E_i$$K_{1,3}$$3$$P_4$

Ich glaube, ich habe eines Tages ein Papier gesehen, in dem sich dieses Problem als NP-vollständig erwiesen hat, aber ich kann es nicht mehr finden, und ich kann mich nicht erinnern, ob dieses Ergebnis auf kubische Graphen zutrifft. In einer verwandten Angelegenheit ist mir bekannt, dass das Aufteilen eines zweigeteilten Graphen in Klauen durch Kanten NP-vollständig ist (siehe Dyer und Frieze ). Hat jemand eine Referenz für das Problem, das ich beschreibe, oder etwas, das damit zusammenhängt (dh dasselbe Problem in einer anderen Diagrammklasse, das ich dann versuchen könnte, auf kubische Diagramme zu reduzieren)?

Dies ist keine Antwort auf die Komplexität des Problems, aber es zeigt zumindest, dass die Komplexität möglicherweise nichttrivial ist: Es ist ein Beispiel für ein kubisches Diagramm, das nicht in Pfade und Klauen unterteilt werden kann.

_{(Quelle: uci.edu )}

Innerhalb jedes seiner drei Vorsprünge kann jede Unterteilung in Pfade und Klauen nur sechs der sieben Kanten verwenden. Die verbleibenden sechs Mittelkanten haben die Form einer Klaue, wobei jede Kante unterteilt ist und nicht in Pfade und Klauen unterteilt werden kann.

ETA : Die oben gezeigte Grafik ist berühmter als ein Beispiel einer kubischen Grafik ohne perfekte Übereinstimmung. Aber jeder kubische Graph mit einer perfekten Übereinstimmung hat eine Zerlegung in Pfade (auch wenn keine Klauen verwendet werden). Nach König's Theorem beinhaltet dies alle kubischen zweigliedrigen Graphen und nach Petersens Theorem beinhaltet dies alle brückenlosen kubischen Graphen, wobei eine Frage von Joseph Malkevitch in den Kommentaren beantwortet wird.

Der Beweis ist sehr einfach: Wenn M eine perfekte Übereinstimmung in einem kubischen Graphen ist, hinterlässt die Entfernung von M einen 2-regulären Graphen, dh eine disjunkte Vereinigung von Zyklen. Orientiere jeden Zyklus willkürlich und befestige jede Kante uv von M an den Zykluskanten, die u und v in den Ausrichtungen ihrer Zyklen folgen.

In der anderen Richtung gibt es bei einer Zerlegung in Pfade eine perfekte Übereinstimmung: Die Mittelkanten jedes Pfades müssen übereinstimmen, da keine zwei Mittelkanten einen Scheitelpunkt von Grad drei gemeinsam haben können.

(Haftungsausschluss: Möglicherweise war diese Idee bereits in Carsten Thomassens eingeladenem Vortrag auf der GD 2010 enthalten, in dem es um diese Art von Graphenzerlegungsproblem ging.)

(Zusätzlich zum Haftungsausschluss (von Anthony Labarre): Die "Orientierungsidee" für den Übergang von einer perfekten Zuordnung zu einer Unterteilung in Pfade wird in diesem Artikel von Jünger, Reinelt und Pulleyblank vorgestellt , die sie WH Cunningham zuschreiben.)

$k$$k\geq 3$$k=3$$2$$3$

Dies war eigentlich nicht das Ende der Geschichte: Wenn der kubische Graph zweiteilig ist, ist es einfach, seinen Kantensatz nur mit Klauen zu unterteilen, indem Sie einen Satz der Zweiteiligkeit auswählen und ihn zu einem Satz von "Klauenzentren" machen. Das allgemeine Problem ist in der Tat schwer, was mit einer Reduktion von CUBIC PLANAR MONOTONE 1-IN-3 SATISFIABILITY bewiesen werden kann. Alle Details sind auf arxiv frei zugänglich .

Vielleicht ist dieses Papier von Interesse:

Kleinschmidt, Peter Reguläre Partitionen von regulären Graphen. Kanada. Mathematik. Stier. 21 (1978), no. 2, 177–181.

Es handelt sich um Graphen, die als Vereinigung von "Z-Pfaden" der Länge 3 geschrieben werden können. (Insbesondere planare, 3-wertige, 3-zusammenhängende Graphen, kubische 3-Polytope.)