Complexidade da contagem de todos os subgráficos conectados

Seja G um gráfico conectado.

Qual é a complexidade de contar todos os subgráficos conectados se G for dos seguintes tipos?

G é geral.

G é plano.

G é bipartido.

Eu não ligo para nenhuma estrutura ou ..., só preciso contar todos os subgráficos conectados! Também estou interessado na complexidade de contar todos os subgráficos conectados com exatamente k nós em G.

Ponteiros para papéis e livros também são bem-vindos!

cc.complexity-theory graph-theory counting-complexity marjoonjan
fonte

Você está ciente de que a lista na pergunta não está formatada corretamente? meta.cstheory.stackexchange.com/questions/300/… Se você não se importa com a formatação, tudo bem. Mas não tenho certeza se alguém deseja gastar tempo para responder à sua pergunta quando você não deseja gastar tempo para formatá-la corretamente. (Não estou dizendo que sei a resposta.)

Tsuyoshi Ito

Além disso, você se preocupa em enumerar subgráficos conectados de tamanho / ordem / estrutura / ... arbitrários, ou deseja que eles sejam abrangidos ou qualquer outra coisa?

Anthony Labarre

Parece funcionar na contagem de subgráficos de extensão conectados . Página 32 de Ligações de Sokal "multivariada Tutte polinomiais" abrangendo subgráfico polinomial a confiabilidade polinomial que tem uma literatura enorme

Yaroslav Bulatov

Sinto muito, minha resposta anterior sobre o uso do teorema de Kirchhoff estava errada. Pensei em um argumento de inclusão-exclusão, mas isso pode ser inviável.

didest

Este artigo não é exatamente o que você solicitou, mas o artigo e suas referências podem ajudar no desenvolvimento de algumas idéias.

MS Dousti

Respostas:

Galês afirma que o problema # P é concluído mesmo no caso mais restrito (contando o número de subgráficos conectados de um gráfico bipartido planar). Veja o final da página 305 em Galês, Dominic (1997), "Approximate Counting", Surveys in Combinatorics , Bailey, RA, ed., Cambridge University Press, pp. 287-324.

No contexto, porém, pergunto-me se ele realmente quer dizer subgráficos de extensão conectados. E isso me leva a pensar em qual versão do problema você deseja: subgráficos de abrangência conectados, subgrafos conectados que não precisam ser abrangidos ou subgráficos induzidos conectados?

David Eppstein
fonte

Esta é uma resposta à resposta de Davi. Ainda sem ter analisado esse livro, acho que o problema é contar subgráficos de extensão conectados, porque esse é o ponto x = 1 y = 2 do polinômio de Tutte, e o autor estava interessado nisso. Mas, na verdade, acho que esses três problemas se reduzem facilmente com a contagem do problema do subgrafo de extensão conectado. As reduções a seguir devem funcionar para contagem exata ou aproximação, embora eu ache que o problema de aproximação ainda esteja aberto.

$K_A$ $A$

$\#P$

Colin McQuillan
fonte

Você não precisa anexar uma camarilha, certo? Você pode anexar qualquer coisa que tenha muitos subgráficos conectados, desde que você anexe a mesma coisa a cada vértice. Portanto, você pode fazer essas reduções enquanto preserva a planaridade e a bipartididade.

David Eppstein