Gráficos cúbicos de particionamento de arestas em garras e caminhos

12

Novamente, um problema de particionamento de borda cuja complexidade me interessa, motivada por uma pergunta anterior minha .


Entrada: um gráfico cúbicoG=(V,E)

Pergunta: existe uma partição de em , de modo que o subgráfico induzido por cada seja uma garra (ou seja, , freqüentemente chamada de estrela) ou um caminho de ( ie )?E 1 , E 2 , , E s E i K 1 , 3 3 P 4EE1,E2,,EsEiK1,33P4


Acho que vi um artigo um dia em que esse problema foi comprovado como NP-completo, mas não consigo mais encontrá-lo e não me lembro se esse resultado se aplicava a gráficos cúbicos. Em um assunto relacionado, estou ciente de que o particionamento de borda de um gráfico bipartido em garras é NP completo (consulte Dyer e Frieze ). Alguém tem uma referência para o problema que eu descrevo, ou algo relacionado (ou seja, o mesmo problema em outra classe de gráfico, que eu poderia tentar reduzir a gráficos cúbicos)?

Anthony Labarre
fonte
2
Isso pode ajudá-lo: Partição de Borda em e é -Complete. K 1 , 3 N PK3K1,3NP
Mohammad Al-Turkistany
turkistany, você poderia adicionar uma referência a isso ao seu comentário?
Anthony Labarre
1
Anthony, Aqui está o link ( andrew.cmu.edu/user/jblocki/K-Anonymity.pdf )
Mohammad Al-Turkistany
Oh, certo. Esse é o artigo que eu lembrei, que pensei erroneamente tratar exatamente o meu problema. Bem, obrigado de qualquer maneira para o lembrete, talvez eu possa de fato fazer algo com ele ...
Anthony Labarre
1
Você tem um exemplo de um gráfico cúbico que não pode ser particionado dessa maneira?
David Davidpspstein

Respostas:

15

Isso não é uma resposta para a complexidade do problema, mas pelo menos mostra que a complexidade tem uma chance de não ser trivial: é um exemplo de um gráfico cúbico que não pode ser particionado em caminhos e garras.

texto alternativo
(fonte: uci.edu )

Dentro de cada um de seus três lóbulos, qualquer partição em caminhos e garras pode usar apenas seis das sete arestas. As seis arestas centrais restantes assumem a forma de uma garra com cada aresta subdividida, que não pode ser dividida em caminhos e garras.

ETA : O gráfico mostrado acima é mais famoso como um exemplo de gráfico cúbico sem uma correspondência perfeita. Mas todo gráfico cúbico com uma correspondência perfeita tem uma decomposição em caminhos (nem mesmo usando garras). Pelo teorema de König, isso inclui todos os gráficos bipartidos cúbicos e pelo teorema de Petersen isso inclui todos os gráficos cúbicos sem ponte, respondendo a uma pergunta de Joseph Malkevitch nos comentários.

A prova é muito simples: se M é uma combinação perfeita em um gráfico cúbico, a remoção de M deixa um gráfico 2-regular, ou seja, uma união disjunta de ciclos. Oriente cada ciclo arbitrariamente e conecte cada aresta uv de M às arestas do ciclo que seguem u e v nas orientações de seus ciclos.

Na outra direção, se houver uma decomposição em caminhos, haverá uma correspondência perfeita: as arestas do meio de cada caminho devem ser uma correspondência, pois nenhuma aresta do meio pode compartilhar um vértice de grau três.

(Aviso: esta ideia pode já estar presente na palestra convidada de Carsten Thomassen na GD 2010, que tratava desse tipo de problema de decomposição de gráficos.)

(além do aviso de isenção de responsabilidade (de Anthony Labarre): a "ideia de orientação" para passar de uma combinação perfeita para uma partição em caminhos aparece neste artigo por Jünger, Reinelt e Pulleyblank , que a atribuem a WH Cunningham.)

David Eppstein
fonte
Este belo exemplo enquanto o avião não está conectado 2. Um próximo passo pode ser observar os gráficos conectados ao plano 2.
Joseph Malkevitch
Obrigado por seus comentários valiosos e esta contra-exemplo, eu posso parar de olhar para um ;-)
Anthony Labarre
Você pode achar útil que esses lóbulos (o gráfico único com seqüência de graus 1,3,3,3,3,3) possam (eu acho) serem usados ​​no lugar de um loop-on-edge em uma generalização multigráfica de seu problema.
Colin McQuillan
9

kk3k=323

Na verdade, esse não era o fim da história: se o gráfico cúbico é bipartido, é fácil particionar seu conjunto de arestas usando apenas garras, selecionando um conjunto da bipartição e transformando-o em um "centro de garras". O problema geral é realmente difícil, o que pode ser provado usando uma redução da SATISFIABILIDADE 1-EM-3 DO MONOTONE CUBIC PLANAR. Todos os detalhes são acessíveis gratuitamente no arxiv .

Anthony Labarre
fonte
6

Talvez este artigo possa ser interessante:

Kleinschmidt, Peter Partições regulares de gráficos regulares. Canadá. Matemática. Touro. 21 (1978), n. 2, 177-181.

Ele lida com gráficos que podem ser escritos como a união de "caminhos Z" de comprimento 3. (Especificamente, 3-polítopos gráficos cúbicos planares, com 3 valentes e 3 conectados).

Joseph Malkevitch
fonte