NP completa problemas gráficos sobre propriedades estruturais

(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.$\mathcal{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.$\mathcal{NP}$$\mathcal{P}$

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 induzido$1$ ? (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á).$\pi$$\pi$$\pi$

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.$C$$C$$NP$$NP$

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.

$NP$$NP$

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.

$NP$$P$

$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.