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

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? $G=(V,E)$ $k$ $S\subseteq V$ $|S|=k$ $G$ $S$

Observe que o problema é obviamente fácil para uma constante pois todos os subgráficos de tamanho podem ser enumerados no tempo . 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. $k$ $k$ ${|V| \choose 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 não-invariantes e $k$ definidas como vértices.

Quando

k = \log n

$k=\log n$ , o número de tais subconjuntos é

(\binom{| V |}{\log n}) \leq n^{\log n}

$\binom{|V|}{\log n}\leq n^{\log n}$ 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 (2^{\log n}) = O (n)

$O(2^{\log n})=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 = θ (\frac{n}{\log n})

$k=\theta(\frac{n}{\log n})$ ; nesse caso, a abordagem ingênua leva

2^{O (n)}

$2^{O(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

2^{n^{Ω (1)}}

$2^{n^{\Omega(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

$k$ tal que, a abordagem ingênua leve

O (2^{n})

$O(2^n)$ 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 (2^{n})

$O(2^n)$

Tsuyoshi Ito

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:

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

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 $\mathbb{A}$ $G$ $k\in \mathbb{N}$ $\epsilon >0$ $\delta \in (0,1)$ $z$ $k$ $\mathbb{A}$ $z'$

P (z^{'} \in [(1 - ϵ) z, (1 + ϵ) z]) \geq 1 - δ,

$\begin{equation} \mathbb{P}(z' \in [(1-\epsilon)z,(1+\epsilon)z]) \geq 1-\delta, \end{equation}$

f (k) \cdot g (n, ϵ^{- 1}, \log δ^{- 1})

$f(k)\cdot g(n,\epsilon^{-1},\log \delta^{-1})$

f

$f$

g

$g$ é 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. $\Phi$

{S \subseteq V (G) ∣ | S | = k \land Φ (G [S])},

$\begin{equation} \{S \subseteq V(G) \mid |S| =k \wedge \Phi(G[S])\}, \end{equation}$

Φ

$\Phi$

Φ

$\Phi$

Radu Curticapean
fonte