Particionar um gráfico em ciclos separados por nós

Problema relacionado: O Teorema de Veblen afirma que "Um gráfico admite uma decomposição de ciclo se e somente se for par". Os ciclos são separados por arestas, mas não necessariamente separados por nós. Em outras palavras, "O conjunto de arestas de um gráfico pode ser dividido em ciclos se e somente se todos os vértices tiverem grau uniforme".

Meu Problema: Gostaria de saber se alguém estudou a partição de um gráfico em ciclos separados por nós. Ou seja, particione os vértices de um gráfico em e cada subgráfico induzido por é hamiltoniano. $V$ $G$ $V_1, V_2, \cdots, V_k$ $V_i$

É NP-difícil ou fácil?

Problema mais relacionado: A partição em triângulo é NP-completa. (Página 68 de "Computadores e intratabilidade")

Agradecemos desde já o seu conselho. ^^

cc.complexity-theory graph-theory co.combinatorics Peng Zhang
fonte

Há uma redução fácil da correspondência. Exercício bem conhecido em algoritmos.

Chandra Chekuri

Esse é o seu problema: en.wikipedia.org/wiki/Vertex_cycle_cover ?

Thomas Ahle

@ Thomashole Obrigado, eu não tinha conhecimento dessa página wiki. É chamado de 'capa do ciclo separado' mencionado nessa página da wiki.

Peng Zhang

Uma partição em ciclos separados por vértices é a mesma coisa que um subgráfico 2-regular, mais comumente conhecido como um fator 2. Pode ser encontrado (se existir) no tempo polinomial por um algoritmo baseado na correspondência. ~~Por exemplo, veja este link .~~

ETA novembro de 2013: Parece a partir dos comentários abaixo que a redução da fonte vinculada acima está errada. No entanto, a declaração de que o problema pode ser reduzido a uma correspondência perfeita permanece correta. A redução correta está em WT Tutte (1954), "Uma prova curta do teorema dos fatores para gráficos finitos", Canadian J. Math. 6: 347–352 .

Substitua cada vértice pelo grau por um gráfico bipartido completo $v$ $d$ , e represente cada arestado gráfico original por uma aresta de um vértice de a um vértice de (no lado da bipartição comvértices) de maneira que cada vértice de desse lado da bipartição tem exatamente um desses incidentes de ponta. $G_v=K_{d,\,d-2}$ $uv$ $G_u$ $G_v$ $d$ $G_v$

Então, uma correspondência perfeita no gráfico modificado deve corresponder aos vértices lado da bipartição de com dos vértices do outro lado, deixando exatamente dois vértices livres que precisam ser correspondidos com seus vizinhos em outros subgráficos . Dessa maneira, as combinações perfeitas do gráfico modificado correspondem 1 a 1 com capas de ciclo do gráfico original. $d-2$ $G_v$ $d-2$ $d$ $G_u$

David Eppstein
fonte

Eu não entendo. Todas as menções que encontrei, desse algoritmo, começam computando um tour de euler. No entanto, existem muitos gráficos que podem ser cobertos por ciclos sem ter um tour por euler. Também está em P se não exigirmos que todas as arestas sejam usadas?

Thomas Ahle

Você leu o artigo ao qual vinculei? Não vejo menção aos passeios de Euler por lá.

precisa

É um pouco difícil de entender. Quando você constrói

mudando cada aresta

para uma aresta de

para

(

), como você sabe qual extremidade colocar em

e qual colocar em

? O documento parece "apenas tomar o segundo", mas não é um grafo dirigido ..

E^{'}

$E'$

(i, j)

$(i,j)$

V

$V$

V^{'}

$V'$

(i, j^{'})

$(i,j')$

V

$V$

V^{'}

$V'$

Thomas Ahle

Quero dizer, eu também poderia converter todas as arestas não direcionadas em arestas direcionadas em cada direção, mas a correspondência poderia me dar muitos ciclos de "comprimento 2", não?

Thomas Ahle

@ThomasAhle aparentemente misturou termos; que eu quis dizer é um

-Regular spanning gráfico, aka

factor

k

$k$

k

$k$

Manfred Weis

Particionar um gráfico em ciclos separados por nós

Respostas: