Referência para gráficos livres de orifícios ímpares e anti-orifícios?

16

Gráficos livres de X são aqueles que não contêm gráfico de X como um subgrafo induzido. Um buraco é um ciclo com pelo menos 4 vértices. Um buraco ímpar é um buraco com um número ímpar de vértices. Um anti - furo é o complemento de um buraco.

Os gráficos livres de orifícios ímpares e orifícios ímpares são precisamente os gráficos perfeitos; esse é o teorema do gráfico perfeito forte . É possível encontrar o maior conjunto independente (e a maior clique) em um gráfico perfeito em tempo polinomial, mas o único método conhecido para fazer isso exige a construção de um programa semidefinido para calcular o número teta de Lovász .

Os gráficos livres de orifícios (anti furo) são chamados de cordas fracamente e constituem uma classe bastante fácil para muitos problemas (incluindo INDEPENDENT SET e CLIQUE ).

Alguém sabe se foram estudados ou escritos gráficos livres de buracos estranhos e anti-buracos?

Esses gráficos ocorrem naturalmente em problemas de satisfação de restrições, nos quais o gráfico de variáveis ​​relacionadas forma uma árvore. Tais problemas são bastante fáceis, por isso seria bom se houvesse uma maneira de encontrar uma maior clique independente de conjunto de gráficos nessa família sem precisar calcular o teta de Lovász.

Equivalentemente, deseja-se encontrar um maior conjunto independente para gráficos livres de furos (anti-furo). Hsien-Chih Chang mostra abaixo por que essa é uma classe mais interessante para o CONJUNTO INDEPENDENTE do que os gráficos livres de buracos ímpares e anti-buracos.

András Salamon
fonte

Respostas:

12

De fato, é relativamente fácil. Em vez de estudar o problema do conjunto independente em gráficos sem orifícios (anti-furo), pegamos um complemento dos gráficos e tentamos encontrar um clique máximo nele. Assim, torna-se o problema máximo de clique em gráficos sem orifícios (orifícios, orifícios ímpares).

Na seção 2 do artigo " Bairros triangulados em gráficos sem buracos ", de Silva e Vuskovic, eles afirmaram que Farber mostra pela primeira vez

O(n2)

Então, seu principal teorema afirmou que

O(n+m)O(n2m)

O(n2m)

K2,m¯


Editar:

Oh, outro pensamento surgiu. Os gráficos sem furos (furos, furos anti-ímpares) são quase fracamente cordais no seguinte sentido: uma vez que livre de 4 furos implica apenas restos anti-furos com tamanho 4 ~ 7 (qualquer k-anti-furo com tamanho> 7 contém um orifício de 4) e também é livre de orifícios estranhos, o que restringe o tamanho dos orifícios a 4 e 6; quase não há orifícios / anti furos no gráfico! Assim, um algoritmo poli-tempo parece plausível para tais gráficos.

Hsien-Chih Chang 張顯 之
fonte
K2,mm2
11
Obrigado! Olhando novamente para o meu resultado com Peter Jeavons, mostramos que os problemas de restrição estruturados em árvore produzem gráficos livres de furos (anti-furo) nos quais se deseja encontrar o maior conjunto independente. Tornarei a pergunta mais precisa - sugeri incorretamente que IS era o problema que se queria resolver.
András Salamon
@ AndrásSalamon você pode dar acesso aberto a pré-impressões do seu trabalho sobre este tópico? Eu não poderia acesso através da minha universidade procuração nem
Diego de Estrada
@DiegodeEstrada: ficaria feliz em enviar uma pré-impressão do nosso artigo do CP 2008, basta enviar-me um e-mail. No entanto, é realmente um documento de restrições, por isso pode não ser tão interessante para você.
András Salamon