Complexidade computacional da contagem de subgráficos induzidos que admitem combinações perfeitas

25

Dado um gráfico não-direcionado e não ponderado e um número inteiro par , qual é a complexidade computacional da contagem de conjuntos de vértices modo que e o subgrafo de restrito ao conjunto de vértices admite uma combinação perfeita? A complexidade é # P-completa? Existe uma referência para este problema?k S V | S | = k G SG=(V,E)kSV|S|=kGS

Observe que o problema é obviamente fácil para uma constante pois todos os subgráficos de tamanho podem ser enumerados no tempo {| V | \ escolha k} . Observe também que o problema é diferente de contar o número de combinações perfeitas. A razão é que um conjunto de vértices que admite uma correspondência perfeita pode ter vários números de correspondências perfeitas.kkk(|V|k)

Outra maneira de declarar o problema é a seguinte. Uma correspondência é chamada de correspondência k se corresponder a k vértices. Duas correspondências M e M são `` conjunto de vértices não invariantes' 'se os conjuntos de vértices correspondidos por M e M não forem idênticos. Queremos contar o número total de correspondências k não-invariantes e kdefinidas como vértices.

ha
fonte
Quando k=logn , o número de tais subconjuntos é (|V|logn)nlogn e verificando se o gráfico induzido pelo subconjunto possui uma correspondência perfeita usando as instruções de Tutte. a caracterização leva O(2logn)=O(n) tempo, portanto, é improvável que seja NP-completo, a menos que a hipótese de tempo exponencial esteja errada. Portanto, o caso interessante é quando k=θ(nlogn) ; nesse caso, a abordagem ingênua leva 2O(n) tempo, se você estiver procurando pela integridade de #P.
Sajin Koroth
@ Sarah Koroth: Eu não sigo a última frase do seu comentário. Por exemplo, se k = √n, a abordagem ingênua leva 2nΩ(1) tempo, e eu não acho que isso dê qualquer evidência contra ser # P-completo.
Tsuyoshi Ito
@TsuyoshiIto: Sim, você está correto. Deveria ter sido "escolha um k tal que, a abordagem ingênua leve O(2n) tempo".
Sajin Koroth 22/03/12
@Sajin Koroth: Por que escolher um valor de k de tal modo que a abordagem ingênua leva tempo ? Fazer isso provavelmente não dói, mas não vejo por que alguém deveria fazer isso. O(2n)
Tsuyoshi Ito
4
Parece que a maioria dos problemas do tipo "como o homem induziu subgráficos de tamanho k têm propriedade X?" são difíceis. Até a propriedade "tem uma aresta" é difícil ("Tem uma aresta" resolve "não tem uma aresta" que é "é um gráfico completo" no duelo ... resolve MAX CLIQUE). Isso realmente faz parecer que "tem uma correspondência perfeita" também será difícil, mas encontrar uma prova é difícil no momento.
bbejot

Respostas:

6

O problema é # P-completo. Segue-se do último parágrafo da página 2 do seguinte artigo:

CJ Colbourn, JS Provan e D. Vertigan, A complexidade da computação do polinômio de Tutte em matróides transversais, Combinatorica 15 (1995), n. 1, 1-10.

http://www.springerlink.com/content/wk55t6873054232q/

ha
fonte
6

O problema admite um FPTRAS. Este é um algoritmo aleatório que obtém um gráfico , um parâmetro e números racionais e como entradas. Se é o número de conjuntos de -vertex que você está procurando, então gera um número tal que e o faz no tempo , onde é alguma função computável G k N ϵ > 0 δ ( 0 , 1 ) z k A z P ( z [ ( 1 - ϵ ) z , ( 1 + ϵ ) z ] ) 1 - δ ,AGkNϵ>0δ(0,1)zkAz

P(z[(1ϵ)z,(1+ϵ)z])1δ,
f gf(k)g(n,ϵ1,logδ1)fg é algum polinômio.

Isto segue de Thm. 3.1 in (Jerrum, Meeks 13) : Dada uma propriedade de gráficos, há um FPTRAS, com a mesma entrada acima, que se aproxima do tamanho do conjunto desde que seja computável, monótono e todos os seus gráficos com margens mínimas limitem a largura da árvore. Todas as três condições são válidas se for a propriedade gráfica de admitir uma correspondência perfeita.{ S V ( L ) | | S | = k Φ ( G [ S ] ) } , Φ ΦΦ

{SV(G)|S|=kΦ(G[S])},
ΦΦ
Radu Curticapean
fonte