NP completa problemas gráficos sobre propriedades estruturais

20

(Esta pergunta é um pouco de "pesquisa".)

Atualmente, estou trabalhando em um problema em que estou tentando particionar as bordas de um torneio em dois sets, os quais são necessários para cumprir algumas propriedades estruturais. O problema "parece" bastante difícil, e espero que seja -completo.Por alguma razão, estou tendo dificuldades para encontrar problemas semelhantes na literatura.NP

Um exemplo de um problema que eu consideraria comparável ao que estou lidando:

Dado um torneio ponderado , existe um arco de feedback definido em cujas bordas atendem à desigualdade do triângulo?G=(V,E,w)G

Observe a diferença no problema tradicional do conjunto de arcos de feedback: não me importo com o tamanho do conjunto, mas me importo se o conjunto em si possui uma determinada propriedade estrutural.

Você encontrou algum problema de decisão semelhante a isso? Você se lembra se eles eram completos ou em ? Toda e qualquer ajuda é apreciada.NPP

G. Bach
fonte
Talvez você possa explicar as propriedades estruturais do seu problema, existem muitos especialistas aqui que são familiarizados com provas NPC e em vez de uma referência que você poderia começar uma prova NPC :-)
Marzio De Biasi
@MarzioDeBiasi Gostaria muito de evitar uma prova do problema com o qual estou lidando; é a primeira vez que eu estou fazendo pesquisa real e eu gostaria de ver onde posso chegar no meu próprio :)
G. Bach
1
Para mim, a pergunta parece vaga demais e é difícil adivinhar o que realmente é perguntado. Provavelmente, a questão deve ser mais específica: o que você quer dizer com "se parece com isso" e o que você quer dizer com "um arco de feedback definido em G cujas bordas atendem à desigualdade do triângulo"; você quer uma referência sobre o problema do conjunto de arcos de feedback ou sobre outro problema?
Yoshio Okamoto
1
@YoshioOkamoto Percebo que há alguma ambiguidade na questão, e esperava que o exemplo esclarecesse parte disso. Por "arco de feedback definido em G cujas bordas atendem à desigualdade do triângulo", quero dizer: se é um arco de feedback definido e ( a , b ) , ( b , c ) , ( a , c ) F , então w ( a , b ) + w ( b , c ) w ( a , c )F(a,b)(b,c)(a,c) Fw(a,b)+w(b,c)w(a,c)precisa segurar para preencher essa propriedade. Anteriormente, eu só encontrei problemas do tipo | F | k , mas quero que F tenha uma propriedade não relacionada à sua cardinalidade. F|F|kF
G. Bach
alguém pode dar um link / ref para "o problema de conjunto de arco de feedback tradicional" ...?
vzn

Respostas:

19

Eu acho que existem muitos problemas semelhantes. Aqui estão dois na versão de vértice e um na versão de borda:

1) Um determinado gráfico possui um conjunto de vértices de feedback independente ? (não nos importamos com o tamanho do conjunto). Esse problema é NP-completo; a prova pode ser derivada da prova do Teorema 2.1 em Garey, Johnson & Stockmeyer .

2) Um determinado gráfico possui uma cobertura de vértice que induz uma árvore ? (não nos importamos com o tamanho do conjunto). Este artigo fornece uma prova de completude da PN para esse problema (Teorema 2); mesmo para gráficos bipartidos.

3) Um determinado gráfico tem uma aresta dominante definida cujas arestas formam um subgráfico regular induzido1 ? (também conhecido como dominando correspondência induzida ou dominando borda eficiente; a versão do vértice é dada na segunda resposta por Mohammad. Novamente, não nos importamos com o tamanho do conjunto). Esse problema é NP-completo (bem conhecido, primeiro foi provado aqui ), mesmo para gráficos bipartidos planares.

Os dois primeiros problemas são exemplos particulares da classe de problemas denominada stable- : Seja π uma propriedade do gráfico. Um dado gráfico possui uma cobertura de vértice satisfazendo π ? Mais casos de NP completos, bem como casos de polinômios solucionáveis, podem ser encontrados neste e neste artigo (e nas referências fornecidas lá).πππ

vb le
fonte
5
Esses são exatamente os tipos de problemas que estou procurando!
G. Bach
3
@ G.Bach Como isso responde exatamente à sua pergunta, sugiro que você aceite a resposta e conceda a recompensa.
Mohammad Al-Turkistany
@ MohammadAl-Turkistany Concordo; por alguma razão, só poderei conceder a recompensa em uma hora.
G. Bach
4
Obrigado pelo seu bom post. Por um tempo, pensei nas mesmas linhas.
Mohammad Al-Turkistany
4

Outro exemplo é o problema eficiente do conjunto dominante, também conhecido como código 1 perfeito nos gráficos. O problema é determinar a existência de um conjunto dominante no gráfico não direcionado, de modo que o caminho mais curto entre quaisquer dois nós no conjunto dominante C seja pelo menos 3 (arestas). O problema foi provado ser N P -Complete independentemente por muitos investigadores. O problema permanece N P -Complete mesmo para grafos planares cúbicos.CCNPNP

DW Bange, AE Barkauskas e PJ Slater. Conjuntos dominantes eficientes em gráficos . Aplicações da matemática discreta, Proc. 3rd SIAM Conf., Clemson / Carolina do Sul 1986, 189-199 (1988)., 1988.

Mohammad Al-Turkistany
fonte
Outras variantes do conjunto dominante são o conjunto dominante conectado e o conjunto dominante independente .
Radu Curticapean
2
@RaduCurticapean Mas, por essas variantes, você se importa com o tamanho da solução.
vb le
Sim, eu esqueci isso.
Radu Curticapean
3

NPNP

Um furo é um ciclo sem corda de comprimento maior que três. Um ciclo no gráfico direcionado é sem corda se seu comprimento for maior que 3 e nenhum dos seus vértices for unido por uma aresta do gráfico direcionado que não pertence ao ciclo.

NPP

NP

A importância de detectar a estrutura do buraco ímpar nos gráficos é destacada pela recente descoberta do Teorema do Gráfico Perfeito Forte . Mostra que um gráfico é perfeito se, e somente se, nem seu gráfico complementar tiver um furo ímpar.

Mohammad Al-Turkistany
fonte
Um ciclo é um ciclo induzido se e somente se for um ciclo sem corda (também chamado de furo).
Mohammad Al-Turkistany
1
As duas respostas parecem o tipo de problema que estou procurando, obrigado!
G. Bach