3-Clique-Partition für Diagramme mit festem Durchmesser

11

Das 3-Clique-Partitionsproblem ist das Problem der Bestimmung, ob die Eckpunkte eines Graphen, beispielsweise , in 3 Cliquen aufgeteilt werden können. Dieses Problem ist NP-hart durch eine einfache Reduzierung des 3-Färbbarkeitsproblems. Es ist nicht schwer zu erkennen, dass die Antwort auf dieses Problem einfach ist, wenn diam ( G ) = 1 oder diam ( G ) > 5 ist . Das Problem bleibt NP-hart, wenn diam ( G ) = 2 durch eine einfache Reduktion von sich selbst (wenn ein Graph G gegeben ist , füge einen Scheitelpunkt hinzu und verbinde ihn mit allen anderen Scheitelpunkten).Gdiam(G)=1diam(G)>5diam(G)=2G

Was ist die Komplexität dieses Problems für Graphen mit für 3 p 5 ?diam(G)=p3p5

Babak Behsaz
quelle

Antworten:

6

Das Problem scheint in .P

Nehmen Sie zwei Eckpunkte , v mit einem Abstand von genau 3 (ein solches Paar muss existieren, wenn p 3 ist ). Sie müssen unterschiedliche Farben haben (ich werde R, G, B verwenden, um 3 Farben zu bezeichnen, und die Eckpunkte in derselben Clique sind in derselben Farbe gefärbt). Wlog nimmt an, dass u rot und v grün gefärbt ist.uvp3uv

Γ(u)uΓ(v)VΓ(u)Γ(v)uvuvvmuss entweder grün oder blau gefärbt sein. Jeder Scheitelpunkt hat jetzt höchstens zwei Möglichkeiten, daher wird das Problem zu einer 2-SAT-Instanz, die wir in Polynomzeit lösen können.

Rong Ge
quelle
1
Können Sie die entsprechende 2-SAT-Formulierung beschreiben?
user5153
1
B(v)vuv(B(v)B(u))(B(v)¯B(u)¯)
Babak Behsaz