Complejidad computacional de contar subgrafías inducidas que admiten emparejamientos perfectos

Dado un gráfico no dirigido y no ponderado y un entero par , ¿cuál es la complejidad computacional de contar conjuntos de vértices tal que y el subgrafo de restringido al conjunto de vértices admite una combinación perfecta? ¿La complejidad # P-completa? ¿Hay alguna referencia para este problema? $G=(V,E)$ $k$ $S\subseteq V$ $|S|=k$ $G$ $S$

Tenga en cuenta que el problema es, por supuesto, fácil para una constante porque entonces todas las subgrafías de tamaño se pueden enumerar en el tiempo . También tenga en cuenta que el problema es diferente de contar el número de coincidencias perfectas. La razón es que un conjunto de vértices que admite una coincidencia perfecta puede tener un número múltiple de coincidencias perfectas. $k$ $k$ ${|V| \choose k}$

Otra forma de plantear el problema es la siguiente. Una coincidencia se llama $k$ coincidencia si coincide con $k$ vértices. Dos coincidencias $M$ y $M'$ son `` conjunto de vértices no invariante' 'si los conjuntos de vértices que coinciden con $M$ y $M'$ no son idénticos. Queremos contar el número total de coincidencias conjunto de vértices no invariantes $k$ .

cc.complexity-theory co.combinatorics counting-complexity decir ah
fuente

Cuando

k = \log n

$k=\log n$ , el número de tales subconjuntos es

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

$\binom{|V|}{\log n}\leq n^{\log n}$ , y verificando si el gráfico inducido por el subconjunto tiene una coincidencia perfecta usando Tutte la caracterización toma

O (2^{\log n}) = O (n)

$O(2^{\log n})=O(n)$ tiempo, por lo tanto, es poco probable que sea incluso NP completo a menos que la hipótesis del tiempo exponencial sea incorrecta. Por lo tanto, el caso interesante es cuando

k = θ (\frac{n}{\log n})

$k=\theta(\frac{n}{\log n})$ , en cuyo caso el enfoque ingenuo tarda

2^{O (n)}

$2^{O(n)}$ tiempo, si está buscando la completitud #P.

Sajin Koroth

@Sajin Koroth: No sigo la última oración en tu comentario. Por ejemplo, si k = √n, el enfoque ingenuo lleva

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

$2^{n^{\Omega(1)}}$ tiempo, y no creo que esto proporcione ninguna evidencia en contra de que sea # P-completo.

Tsuyoshi Ito

@ TsuyoshiIto: Sí, tienes razón. Debería haber sido "elegir un

k

$k$ tal que, el enfoque ingenuo toma

O (2^{n})

$O(2^n)$ tiempo".

Sajin Koroth

@Sajin Koroth: ¿Por qué debería uno elegir un valor de k tal que el enfoque ingenuo tome tiempo? Hacerlo probablemente no duele, pero no veo por qué uno debería hacer eso.

O (2^{n})

$O(2^n)$

Tsuyoshi Ito

Parece que la mayoría de los problemas del tipo "¿cómo las subgrafías inducidas por el hombre de tamaño k tienen propiedad X?" son difíciles. Incluso la propiedad "tiene una ventaja" es difícil ("Tiene una ventaja" resuelve "no tiene una ventaja" que es "es un gráfico completo" en el duelo ... resuelve CLIQUE MÁXIMO). Esto realmente hace sentir que "tiene una combinación perfecta" también será difícil, pero encontrar una prueba es difícil en este momento.

bbejot

Respuestas:

El problema es # P-completo. Se desprende del último párrafo de la página 2 del siguiente documento:

CJ Colbourn, JS Provan y D. Vertigan, La complejidad de calcular el polinomio de Tutte en matroides transversales, Combinatorica 15 (1995), no. 1, 1–10.

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

decir ah
fuente

El problema admite un FPTRAS. Este es un algoritmo aleatorio que obtiene un gráfico , un parámetro y números racionales y como entradas. Si es el número de -conjuntos de vértices que está buscando, entonces genera un número tal que y lo hace a tiempo , donde es alguna función computable y $\mathbb{A}$ $G$ $k\in \mathbb{N}$ $\epsilon >0$ $\delta \in (0,1)$ $z$ $k$ $\mathbb{A}$ $z'$

PAGS (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$ es un polinomio

Esto se desprende de Thm. 3.1 in (Jerrum, Meeks 13) : Dada una propiedad de gráficos, hay un FPTRAS, con la misma entrada que arriba, que se aproxima al tamaño del conjunto siempre que sea computable, monótono y todos sus gráficos de borde mínimo tengan un ancho de árbol limitado. Las tres condiciones se cumplen si es la propiedad gráfica de admitir una coincidencia perfecta. $\Phi$

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

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

Φ

$\Phi$

Φ

$\Phi$

Radu Curticapean
fuente