Existem aplicações de decomposição modular de grafos na teoria TCS / complexidade?

8

Quais são algumas das aplicações da decomposição modular de gráficos na teoria da complexidade / TCS?

Estou especialmente interessado em seu uso em provas ou limites superior / inferior, se ocorrer.

[1] Decomposição modular de grafos , Wikipedia.

[2] Referências para decomposição modular , TCS.SE.

reference-request graph-theory graph-algorithms application-of-theory cc.complexity-theory vzn
fonte
2
Habib e Paul fizeram uma grande pesquisa sobre as aplicações algorítmicas da decomposição modular: dx.doi.org/10.1016/j.cosrev.2010.01.001 . No entanto, duvido da aplicabilidade da decomposição modular no lado negativo (apenas uma visão tendenciosa pessoal).
Yixin Cao
2
Em nosso resultado recente, que mostra a rastreabilidade parametrizada do problema INTERVAL DELETION (para remover no máximo vértices do gráfico give e transformá-lo em um gráfico de intervalo), a decomposição modular do gráfico desempenha um papel importante. Esse problema recebe muito interesse na comunidade de complexidade parametrizada (embora não na comunidade de complexidade da tradição), e os problemas relacionados às classes de grafos são os candidatos mais naturais das aplicações de decomposição modular de grafos. k
Yixin Cao
@YixinCao um ou ambos podem ser respostas.
Suresh Venkat
A decomposição modular, ou pelo menos a identificação de cliques homogêneos máximos, é importante para decompor gráficos sem garras. Também estou inclinado a acreditar que as decomposições modulares não são úteis para limites inferiores: podemos encontrá-las rapidamente e, uma vez feito isso, basicamente temos uma redução para um gráfico menor. Portanto, podemos começar apenas com o gráfico menor.
Andrew D. King
1
A tese de doutorado mencionada nesta resposta mostra links para a teoria descritiva da complexidade.
Frafl

Respostas:

11

Habib e Paul fizeram uma grande pesquisa sobre as aplicações algorítmicas da decomposição modular de grafos.

k

No entanto, não conheço nenhuma aplicação de decomposição modular de gráfico em provas de limites inferiores e duvido de sua aplicabilidade no lado negativo (apenas uma visão tendenciosa pessoal).

Uma observação final. Até onde eu sei, a maioria dos aplicativos algorítmicos não usa toda a potência da decomposição modular de gráficos. Por exemplo, cliques críticos são os módulos da série no segundo nível de uma árvore de decomposição modular (o primeiro nível consiste em cada vértice); e gêmeos são (não necessariamente fortes) módulos feitos de dois vértices adjacentes.

Yixin Cao
fonte
valeu. da H&P online toc, seção 7, "3 novas aplicações da decomposição modular" - correspondência de padrões / intervalos comuns de duas permutações, genômica comparativa / classificação perfeita por reversões, complexidade parametrizada e reduções de kernel / edição de cluster
vzn