Partição 3-Clique para gráficos de diâmetro fixo

11

O problema da partição de 3 cliques é o problema de determinar se os vértices de um gráfico, digamos , podem ser particionados em 3 grupos. Esse problema é difícil de NP por uma simples redução do problema de 3 cores. Não é difícil ver que a resposta para esse problema é fácil quando ou . O problema permanece NP-difícil quando por uma simples redução de si mesmo (dado um gráfico , adicione um vértice e conecte-o a todos os outros vértices).Gdiam(G)=1diam(G)>5diam(G)=2G

Qual é a complexidade desse problema para gráficos com para ?diam(G)=p3p5

Babak Behsaz
fonte

Respostas:

6

O problema parece estar em .P

Pegue dois vértices , com a distância exatamente 3 (esse par deve existir quando ). Eles devem ter cores diferentes (usarei R, G, B para denotar 3 cores e os vértices na mesma clique são coloridos da mesma cor). O Wlog supõe que tenha a cor Vermelha e tenha a cor Verde.uvp3uv

Agora o restante dos vértices são particionados em 3 conjuntos: (vizinhos de ), e . O terceiro conjunto deve ser colorido em azul, porque eles são adjacentes a nem . Os vizinhos de devem ser coloridos em vermelho ou azul porque não estão adjacentes a , da mesma forma os vizinhos de devem ser coloridos em verde ou azul. Cada vértice agora tem no máximo duas opções; portanto, o problema se torna uma instância 2-SAT que podemos resolver em tempo polinomial.Γ(u)uΓ(v)VΓ(u)Γ(v)uvuvv

Rong Ge
fonte
1
você pode descrever a formulação 2-SAT correspondente?
user5153
1
Seja verdadeiro se, e somente se, colorirmos o vértice azul. Considere dois vértices e não conectados por uma aresta. Suponha que ambos possam ser azuis ou vermelhos. Você deve ter as seguintes cláusulas em sua instância 2-SAT: e . O outro caso em que um deles pode ser azul ou vermelho e o outro azul ou verde é semelhante (você só precisa de uma cláusula). B(v)vuv(B(v)B(u))(B(v)¯B(u)¯)
Babak Behsaz 4/12