o que é fácil para gráficos com exclusão menor?

31

O número aproximado de cores parece ser fácil em gráficos com exclusão menor usando o algoritmo de Jung / Shah. Quais são outros exemplos de problemas difíceis nos gráficos gerais, mas fáceis nos gráficos com exclusão menor?

Atualização 10/24 Parece seguir os resultados de Grohe que a fórmula que é FPT para testar em gráficos de largura de árvore limitada é FPT para testar em gráficos excluídos menores. Agora, a pergunta é: como ela se relaciona com a rastreabilidade de contar tarefas satisfatórias dessa fórmula?

A declaração acima é falsa. MSOL é FPT em gráficos de largura de árvore delimitada, no entanto, a 3-colorability é NP-complete em gráficos planares com pequenas exclusões.

ds.algorithms graph-theory graph-minor Yaroslav Bulatov
fonte

23

O resultado mais geral conhecido é por Grohe. Um resumo foi apresentado em julho de 2010:

Martin Grohe, Definibilidade de ponto fixo e tempo polinomial em gráficos com menores excluídos , LICS 2010. ( PDF )

Em resumo, qualquer declaração que seja expressável na lógica de ponto fixo com contagem possui um algoritmo de tempo polinomial em classes de gráficos com pelo menos um menor excluído. (FP + C é uma lógica de primeira ordem aumentada com um operador de ponto fixo e um predicado que fornece a cardinalidade de conjuntos definíveis de vértices). A idéia principal é que a exclusão de um menor permite que os gráficos da classe tenham ordenado decomposições semelhantes a árvores, que são definíveis na lógica do ponto fixo (sem contar).

~~Portanto, uma grande classe de respostas para sua pergunta pode ser obtida considerando as propriedades que são definíveis no FP + C, mas que são difíceis de contar.~~

Editar: não tenho certeza se isso realmente responde à sua pergunta, menos ainda para a sua atualização. O ponteiro e a declaração do resultado de Grohe estão corretos, mas não acho que o texto destacado seja relevante para sua pergunta. (Agradecemos a Stephan Kreutzer por apontar isso.) Vale a pena esclarecer: você quer um problema de contagem que seja difícil em geral, mas fácil em classes com exclusão de menores, ou um problema de decisão?

András Salamon
fonte

1

Interessante ... Gostaria de saber como é essa decomposição em

árvore

2

Um teorema útil que encontrei é que a propriedade é expressável em FP + C, se for decidível em tempo polinomial no gráfico de dois limites. Agora, a pergunta é: como a complexidade dos problemas de decisão do FP + C se relaciona com a complexidade dos problemas de contagem análoga?

Yaroslav Bulatov 24/10/10

@Yaroslav: Você poderia dar uma referência para isso depois que estiver escrito? Obrigado.

Gphilip 29/10/10

3

Lol, eu realmente não o descobri, eu o "encontrei" na página 2 de "Lógica, Gráficos e Algoritmos" de Grohe

Yaroslav Bulatov

18

Uma propriedade interessante das famílias de grafos fechados menores é que elas têm degenerescência limitada . Isso significa que todos os problemas fáceis em gráficos de degenerescência limitada são fáceis em gráficos de uma família menor fechada.

Assim, por exemplo, descobrir se um gráfico contém um clique do tamanho k é geralmente um problema difícil e os melhores algoritmos são como . No entanto, se sabemos que a degenerescência é uma constante, então k-cliques podem ser encontradas em tempo linear, isto é, tempo O (n). O artigo da Wikipedia sobre o problema do clique também fornece algumas informações sobre isso. (O tempo de execução preciso é algo como .) Esse algoritmo é de Chiba e Nishizeki . $O(n^k)$ $O(k d(G)^k n)$

Outros exemplos podem ser encontrados nesta resposta de David Eppstein no MathOverflow para uma pergunta semelhante sobre gráficos com degenerescência limitada.

Robin Kothari
fonte

5

Meu artigo arxiv.org/abs/1006.5440 apresenta alguns resultados mais recentes ao listar cliques com baixa degenerescência, incluindo o tempo de execução um pouco melhor

para listar todos os cliques máximos.

O (d n 3^{d / 3})

$O(dn3^{d/3})$

David Eppstein

Não consigo ver qual é a relação entre os gráficos de menor fechamento (sua resposta) e de menor exclusão (pergunta). O conjunto de todos os gráficos completos também é pouco fechado, mas eles não são de degenerescência limitada.

Saeed

Fechado menor = excluído menor. Todas as famílias de grafos menores fechados e não triviais têm degenerescência limitada. Eu deveria ter adicionado "não trivial" à minha declaração original.

22613 Robin Ontário

Antes de tudo menor fechado! = Menor excluído (em vez excluído menor menor fechado), caso contrário, você pode fornecer muitos novos algoritmos de aproximação e parametrização para muitas classes densas de gráficos. Além disso, o que são os gráficos fechados menores e não triviais? por exemplo, gráficos de largura de árvore, no máximo, f (| G |) são triviais ou não triviais? ou classe de gráficos densos (que são menores fechados e quase ordenados), são menores triviais fechados ou não-triviais? Sua definição não é clara e o leitor não consegue adivinhar o que está em sua mente (e parte de suas definições está errada, como afirmei no início).

\subset

$\subset$

Saeed

Eu posso lhe dizer o que quero dizer com uma família de grafos pouco fechados.

é menor de

se

puder ser obtido de

excluindo arestas, excluindo vértices isolados ou contraindo arestas. Uma família de gráficos é um conjunto de gráficos não rotulados não direcionados

(geralmente um conjunto infinito).

é uma família fechou-se menor para todos

em

, todos os menores de

também estão em

. Uma família não é trivial se não for o conjunto de todos os gráficos. Os gráficos da largura da árvore

(para a constante

) são fechados pouco, mas os gráficos da largura da árvore

H

$H$

G

$G$

H

$H$

G

$G$

F

$F$

F

$F$

G

$G$

F

$F$

G

$G$

F

$F$

k

$k$

k

$k$

não são geralmente fechados em geral. É assim que eu entendo. Eu poderia estar enganado, é claro.

f (| G |)

$f(|G|)$

Robin Kothari

15

Como complemento, outra propriedade útil para algoritmos em gráficos com exclusão menor é que esses gráficos possuem pequenos separadores . Mais precisamente, devido a

Um algoritmo de tempo linear para encontrar um separador em um gráfico excluindo um menor , Bruce Reed e David R. Wood, ACM Transactions on Algorithms, 2009,

existe um algoritmo de tempo linear de encontrar um separador de tamanho , ou um algoritmo de tempo para encontrar um separador de tamanho . $O(n^{2/3})$ $O(n^{3/2} + m)$ $O(n^{1/2})$

Os separadores são bons para técnicas de programação dinâmica , e muitos problemas NP-completos têm algoritmos rápidos com boa taxa de aproximação, dizem que a solução está dentro de um fator constante do ideal, ou mesmo de um PTAS. Gráficos planares e, em geral, gráficos de gênero limitados são bons pontos de partida ao tentar resolver problemas em gráficos com exclusão menor.

Hsien-Chih Chang 張顯之
fonte

Alguma idéia se os separadores ajudarem a contar o número de cores adequadas?

Yaroslav Bulatov 23/10/10

1

Na verdade, talvez o artigo mencionado por Ian ajude melhor. Uma extensão do resultado está em "Algoritmos de aproximação por decomposição de contração", pelos mesmos autores na SODA '07.

Hsien-Chih Chang # 23/10/10

15

$O(1)$

Teoria Menor do Gráfico Algorítmico: Decomposição, Aproximação e Coloração de Demaine, Hajiaghayi e Kawarabayashi

Este artigo fornece uma versão algorítmica de uma certa decomposição (um pouco complexa para explicar) para gráficos menores excluídos garantidos pelo teorema de Robertson & Seymour, que produz vários desses resultados aprimorados de aproximação. Verifique também as referências nele.

Ian
fonte

Obrigado, isso é muito fascinante ... Eu encontrei uma descrição mais acessível do algoritmo de decomposição em de Grohe "Logic, gráficos e Algoritmos"

Yaroslav Bulatov

0

$K_5$ $K_{3,3}$

$H$ $H$

$K_t$ $(t-1)$ $K_t$ $(t-1)$ $t− 2$

Rupei Xu
fonte

o que é fácil para gráficos com exclusão menor?

Respostas: