3-Clique Partition dla wykresów o stałej średnicy

11

Problem podziału na 3 kliki polega na określeniu, czy wierzchołki wykresu, powiedzmy , można podzielić na 3 kliki. Problem ten jest trudny do wyeliminowania przez proste zmniejszenie z 3-kolorowego problemu. Nietrudno dostrzec, że odpowiedź na ten problem jest łatwa, gdy diam ( G ) = 1 lub diam ( G ) > 5 . Problem pozostaje trudny NP, gdy diam ( G ) = 2 przez zwykłą redukcję od siebie (biorąc pod uwagę wykres G , dodaj wierzchołek i połącz go ze wszystkimi innymi wierzchołkami).Gdiam(G)=1diam(G)>5diam(G)=2G

Jaka jest złożoność tego problemu dla wykresów z dla 3 p 5 ?diam(G)=p3p5

Babak Behsaz
źródło

Odpowiedzi:

6

Problem wydaje się być w .P

Weź dwa wierzchołki , v z odległości dokładnie 3 (taka para musi istnieć, gdy p 3 ). Muszą mieć różne kolory (użyję R, G, B, aby oznaczyć 3 kolory, a wierzchołki tej samej kliki mają ten sam kolor). Wlog zakłada, że u ma kolor czerwony, a v ma kolor zielony.uvp3uv

Γ(u)uΓ(v)VΓ(u)Γ(v)uvuvvmusi być w kolorze zielonym lub niebieskim. Każdy wierzchołek ma teraz co najwyżej dwie możliwości, dlatego problemem staje się instancja 2-SAT, którą możemy rozwiązać w czasie wielomianowym.

Rong Ge
źródło
1
czy możesz opisać odpowiednią formułę 2-SAT?
user5153
1
B(v)vuv(B(v)B(u))(B(v)¯B(u)¯)
Babak Behsaz