Existe um problema fácil para gráficos cúbicos, mas difícil para gráficos com grau máximo 3?

Os gráficos cúbicos são aqueles em que todos os vértices têm grau 3. Eles foram extensivamente estudados e estou ciente de que vários problemas difíceis de NP permanecem difíceis de NP, mesmo restritos a subclasses de gráficos cúbicos, mas alguns outros ficam mais fáceis. Uma superclasse de gráficos cúbicos é a classe de gráficos com grau máximo . $\Delta \leq 3$

Existe algum problema que possa ser resolvido em tempo polinomial para gráficos cúbicos, mas que seja NP-difícil para gráficos com grau máximo ? $\Delta \leq 3$

graph-theory graph-algorithms np-hardness Vinicius dos Santos
fonte

Resposta do degenrato que mostra que pode haver diferentes complexidades (embora nem NP-Hard): Encontrar

é tempo constante em gráficos cúbicos, mas linear em gráficos com

. :-)

δ

$\delta$

Δ \leq 3

$\Delta \le 3$

William Macrae

Bom ponto. :-)

Vinicius dos Santos

Com más escolhas de codificações pode até ser

-Hard quando

, mas será muito mais valioso para encontrar um problema que não depende de uma má codificação, e ainda melhor se o problema é um bem estudado 1.

N P

$NP$

Δ \leq 3

$\Delta \le 3$

precisa

Para expandir o comentário de William, aqui está um problema artificial. Dado um gráfico , a sequência de graus de , interpretada como a codificação de uma instância de 3-SAT, representa uma instância satisfatória? $G$ $G$ (Assumindo que a codificação é tal que a sequência de grau todo-3 representa uma atribuição satisfatório para todos os

.) :-)

n

$n$

Neal Young

Consulte também cstheory.stackexchange.com/questions/1215/… para obter mais inspiração (por exemplo, problemas difíceis em árvores de grau máximo 3, mas triviais se não houver nós de folhas).

Jukka Suomela

Respostas:

Aqui está um razoavelmente natural: em uma entrada , determine se tem um subgrafo regular conectado com pelo menos arestas. Para gráficos tridimensionais, isso é trivial, mas se o grau máximo for 3 e a entrada estiver conectada, não uma árvore e não regular, o maior subgrafo desse tipo é o ciclo mais longo, portanto o problema é NP-completo. $(G,k)$ $G$ $k$

David Eppstein
fonte

"... então a solução é o ciclo mais longo ou o máximo de correspondência ...". Como sua reivindicação depende de k? Não é verdade para todos os k.

Tyson Williams

@ Tyson, ele só precisa ser difícil para um

ser difícil, certo? Por exemplo, tome

. David, você precisa estipular que o subgráfico deve ser conectado? (Caso contrário, qualquer cobertura de ciclo (não apenas um ciclo hamiltoniano) terá

bordas, e determinar a existência de uma tampa de ciclo é em

k

$k$

k = n

$k=n$

n

$n$

P

$P$

Neal Young

David, uma correspondência máxima (de tamanho maior que 1) em G não é um subgrafo conectado de G. Você quer dizer "... o ciclo mais longo ou uma única aresta, ..."?

Tyson Williams

Ok ok Hoje não parece ser um bom dia para eu ser rigorosa - muito peru provavelmente. Eu adicionei um pouco de linguagem para descartar esse caso especial.

precisa

@YininCao Como o gráfico está conectado, mas não é regular, não há como escolher um subgráfico 3-regular. Suponha que sim. Existe um vértice que não foi selecionado, pois o gráfico não é regular. Como o gráfico está conectado, esse vértice está conectado a algum vértice 3 regular que foi selecionado. Mas isso significa que existe um vértice de grau 4, uma contradição.

Tyson Williams