Propriedade gráfica NP-completa que é hereditária, mas não aditiva?

12

Uma propriedade de gráfico é chamada de hereditária se fechada com relação à exclusão de vértices (ou seja, todos os subgráficos induzidos herdam a propriedade). Uma propriedade de gráfico é chamada aditiva se for fechada com relação à obtenção de uniões disjuntas.

Não é difícil encontrar propriedades hereditárias, mas não aditivas. Dois exemplos simples:

$\;\;\;$ (1) O gráfico está completo.

$\;\;\;$ (2) O gráfico não contém dois ciclos separados por vértices.

Nesses casos, é óbvio que a propriedade é herdada por subgráficos induzidos, mas, tendo dois gráficos separados que possuem a propriedade, sua união pode não preservá-la.

Ambos os exemplos acima são propriedades decidíveis pela polytime (embora para (2) seja um pouco menos trivial). Se quisermos propriedades mais difíceis, elas ainda poderão ser criadas seguindo o padrão de (2), mas substituindo os ciclos por tipos de gráficos mais complicados. Em seguida, no entanto, que pode facilmente correr para a situação em que o problema não mesmo permanecer em , com base em hipóteses complexidade padrão, tais como . Parece menos trivial para encontrar um exemplo que estadias dentro , mas ainda é difícil. $NP$ $NP\neq coNP$ $NP$

Pergunta: Você conhece um (de preferência natural) propriedade gráfico -completo que é hereditária, mas não aditivo? $NP$

cc.complexity-theory graph-theory graph-algorithms np Andras Farago
fonte

4

Você já fez várias perguntas agora sobre propriedades "naturais". Pode ser útil entender qual é a motivação para algumas dessas perguntas.

Suresh Venkat

1

@Suresh Gostaria de entender melhor o que torna um problema natural, em oposição a artificial, artificial. Penso que o conceito de naturalidade é uma ponte importante entre teoria e realidade, e vale a pena explorar. O que acho intrigante é que, embora não tenhamos uma definição formal de quais problemas são "naturais", as pessoas geralmente têm um consenso claro sobre se um problema específico é natural ou não. Talvez eu publique uma pergunta separada sobre esse problema, para descobrir mais sobre como os outros o veem.

Andras Farago

9

$k$ $k$

Claramente, a captura de subgráficos induzidos não pode aumentar o tamanho mínimo dessa partição. Por outro lado, quando você toma a união disjunta de dois gráficos, deve-se levar a união da partição para grupos de cada um.

Vinicius dos Santos
fonte

k

$k$

k

$k$

k

$k$

k

$k$

h e r e d i t a r y

$hereditary$

k

$k$

k

$k$

4

k

$k$

k

$k$

1

k = 3

$k=3$

G_{1}

$G_1$

G_{2}

$G_2$

1

Considere este problema

$G$ $P$ $Q$

Permanece NP completo, mesmo que as propriedades sejam hereditárias.

Agora, claramente, uma solução do problema acima para um gráfico também fornece solução para os subgráficos induzidos. Mas, ao obter a união de gráficos da mesma família que G, talvez não seja possível resolver usando essa solução.

Por exemplo, o particionamento de gráficos gerais em gráficos de intervalos unitários separados é NP completo, mas após a união de todas as arestas possíveis (completando o gráfico) resolve o problema trivialmente.

Dibyayan
fonte

1

Observe que a pergunta procura uma propriedade que não seja aditiva. No seu exemplo, nada parece garantir que devem existir dois gráficos que possuem a propriedade, mas a união desunida deles não.

Andras Farago

1

$G = (V,E)$ $C_1,\ldots,C_m$ $C_i$ $V$ $E$ $C_i$

$k \geq 3$ $G$ $k$

$k = 2$

Se (1) for verdadeiro, deverá responder à sua pergunta, pois fornece uma propriedade hereditária, mas claramente não aditiva.

(NOTA ADICIONADA: a conjectura (2) é diferente da "conjectura de cobertura de ciclo duplo" de Szekeres e Seymour, apesar do homonimismo).

Super8
fonte

1

Esta propriedade não é hereditária. A remoção de um vértice pode aumentar o número necessário de ciclos para cobrir todas as arestas, porque o vértice removido pode eliminar um ciclo que foi usado para cobrir muitas arestas. O exemplo mais simples é quando o gráfico inteiro é apenas um ciclo. A remoção de um vértice impossibilita a cobertura de um ciclo, pois não resta nenhum ciclo.

Andras Farago

G

$G$

G

$G$

v

$v$

v

$v$

k

$k$

Propriedade gráfica NP-completa que é hereditária, mas não aditiva?

Respostas: