Relação entre dureza de reconhecimento de uma classe de gráfico e caracterização proibida de subgráficos

Estou pensando em classes de gráficos que podem ser caracterizadas por subgráficos proibidos.

Se uma classe de gráfico possui um conjunto finito de subgráficos proibidos, existe um algoritmo de reconhecimento de tempo polinomial trivial (pode-se usar apenas força bruta). Mas uma família infinita de subgrafos proibidos não implica dureza: existem algumas classes com uma lista infinita de subgrafos proibidos, de modo que o reconhecimento também pode ser testado em tempo polinomial. Gráficos cordais e perfeitos são exemplos, mas, nesses casos, existe uma estrutura "agradável" na família proibida.

Existe alguma relação conhecida entre a dureza do reconhecimento de uma classe e o "mau comportamento" da família proibida? Essa relação deveria existir? Esse "mau comportamento" foi formalizado em algum lugar?

cc.complexity-theory graph-theory np-hardness Vinicius dos Santos
fonte

Respostas:

Embora pareça intuitivo que a lista de subgráficos proibidos (induzidos) para uma classe de gráficos que tem reconhecimento NP-duro deveria possuir alguma complexidade "intrínseca", I recentemente encontrada alguma evidência negativo notável a esta intuição na literatura. $\mathscr{C}$

Talvez o mais simples de descrever seja o seguinte, retirado de um artigo de B. Lévêque, D. Lin, F. Maffray e N. Trotignon .

Seja a família de gráficos que são compostos de um ciclo de comprimento de pelo menos quatro, mais três vértices: dois adjacentes ao mesmo vértice do ciclo e um adjacente ao vértice do ciclo, onde e $F$ $u$ $v$ $u$ $v$ são não consecutivo no ciclo (e sem outras arestas).

Agora seja a família de gráficos que são compostos exatamente da mesma maneira, exceto que você adiciona quatro vértices: dois adjacentes ao mesmo vértice do ciclo (como antes), mas agora dois adjacentes ao mesmo vértice do ciclo, onde novamente e não são consecutivos. $F'$ $u$ $v$ $u$ $v$

Então a classe de gráficos que tem como subgrafos induzidos proibidos tem reconhecimento de tempo polinomial, enquanto o reconhecimento da classe que tem como subgrafos induzidos proibidos é NP-difícil. $F$ $F'$

Portanto, acho difícil conceber qualquer condição geral que uma lista de subgráficos induzidos proibidos tenha que satisfazer quando resultar em uma classe com reconhecimento rígido (NP-), considerando que essa condição terá que separar os "muito semelhantes" e acima. $F$ $F'$

Hugo Nobrega
fonte

Boa resposta - isso é bastante delicado.

Suresh Venkat

Interessante. Existe alguma chance de que isso tenha algo a ver com a expressividade da lógica necessária para descrever o padrão? Estou pensando em algo parecido com linguagens formais, onde a complexidade de uma linguagem pode ser caracterizada de maneira equivalente pela forma como é definida (regexp, gramática formal ...) ou pela máquina necessária para reconhecê-la (autômato, pushdown ...) ou a expressividade da lógica necessária para escrever uma fórmula que caracterize as palavras da linguagem (MSO para linguagens regulares, por exemplo).

A3nm

Essa é uma ideia interessante, mas, novamente, não posso deixar de pensar que

são tão próximos que é difícil imaginar uma maneira de "separá-los" dessa maneira (digamos,

sendo descritível em um idioma que

não é ) Eu poderia ser muito negativo, embora ..! Estou admitindo que estou fazendo "intuição" aqui, então ficaria feliz em provar que estou errado.

F

$F$

F^{'}

$F'$

F

$F$

F^{'}

$F'$

Hugo Nobrega

@ Hugo: uma diferença tangível entre eles é a simetria na caracterização de

- não há como distinguir entre os vértices

. O que acontece se você considerar a família

de ciclos de comprimento pelo menos quatro, mais dois vértices adicionais, adjacentes a verts não consecutivos no ciclo? Restaurar a simetria na direção 'outro' (remover uma vert de

vez de adicionar uma) dificulta novamente?

F^{'}

$F'$

u

$u$

v

$v$

F_{0}

$F_0$

F

$F$

Steven Stadnicki

@ Steven: Acho que não, pode-se detectar gráficos em

adivinhando aleatoriamente 8 nós, formando os dois lados do gráfico, e executar o algoritmo três-em-uma-árvore em três nós, como o do Teorema 3.1. Isso fornece um algoritmo de tempo polinomial para detectar

F_{0}

$F_0$

F_{0}

$F_0$

Hsien-Chih Chang # 14/07

A resposta de @Hugo é muito boa, e aqui quero acrescentar algumas opiniões pessoais.

Existem famílias relacionadas semelhantes aos gráficos da família F e F '. Os gráficos da família B1 no artigo são geralmente chamados de pirâmides. E os gráficos da família B2 geralmente são chamados de prismas. Veja a resposta aqui para uma ilustração. Na literatura de problemas de detecção de subgráficos induzidos, eles foram usados para detectar orifícios pares / ímpares, que são ciclos sem corda com comprimento par / ímpar. Pelo famoso teorema do forte gráfico perfeito, um gráfico G é perfeito se G e o complemento de G não contêm buracos ímpares.

Para as famílias de pirâmides e prismas, de fato, existem diferenças entre elas - uma tem uma subárvore induzida de três folhas e a outra não. Isso é chamado de problema "três em uma árvore" , estudado por Chudnovsky e Seymour. É surpreendente que determinar se existe uma árvore induzida que contém três nós dados é tratável, enquanto o problema da "árvore quatro em uma centrada" é difícil para o NP . (Uma árvore centralizada é uma árvore com no máximo um nó com grau maior que 2.) As diferenças entre F e F 'parecem ser causadas pelo mesmo motivo.

Mas parece que uma caracterização completa ainda é difícil, porque nem sabemos a complexidade de detectar gráficos em algumas das famílias que parece bastante simples, como gráficos sem buracos estranhos (!). E para as famílias que sabemos que existe um algoritmo de tempo polinomial, como gráficos perfeitos e gráficos sem buracos, embora existam estratégias gerais (baseadas em decomposições) para projetar um algoritmo, é preciso fornecer um teorema estrutural específico para eles. Geralmente, esse é um processo dependente da família e, na maioria das vezes, as provas são realmente longas. ( Aqui está um exemplo para o gráfico sem orifícios uniformes, onde o papel tem mais de 90 páginas.)

Ainda assim, seria interessante ter algumas classificações para problemas de detecção de subgráficos induzidos, no sentido como o problema das três em uma árvore.

Hsien-Chih Chang 張顯之
fonte