Problemas de gráficos duros subexponencialmente solucionables

A la luz del resultado reciente de Arora, Barak y Steurer, Algoritmos subexponenciales para juegos únicos y problemas relacionados , me interesan los problemas de gráficos que tienen algoritmos de tiempo subexponenciales pero que no se pueden resolver polinomialmente. Un ejemplo famoso es isomorfismo gráfico que tiene algoritmo subexponencial de $2^{O(n^{1/2} \log n)}$ tiempo de ejecución. Otro ejemplo es el problema log-Clique que se puede resolver en tiempo cuasi-polinomial ( $n^{O(\log n)}$ ).

Estoy buscando ejemplos interesantes y preferiblemente una referencia a encuestas de problemas de gráficos duros subexponenciales (no necesariamente $NP$ -completo). Además, ¿hay algún problema de grafo $NP$ completo con algoritmos de tiempo subexponencial?

Impagliazzo, Paturi y Zane demostraron que la hipótesis del tiempo exponencial implica que Clique, k-Colorability y Vertex Cover necesitan $2^{\Omega(n)}$ tiempo.

Por cierto, el problema de Max Clique, en general, puede resolverse en el tiempo dondeNes el tamaño de la entrada.$2^{\tilde O(\sqrt N)}$$N$

Esto es trivial si el gráfico se representa a través de una matriz de adyacencia, porque entonces , y una búsqueda de fuerza bruta llevará tiempo 2 O ( | V | ) .$N=|V|^2$$2^{O(|V|)}$

Pero podemos obtener el mismo límite incluso si el gráfico está representado por listas de adyacencia, a través de un algoritmo de tiempo de ejecución . Para ver cómo, obtengamos un2 ˜ O ($2^{\tilde O(\sqrt{|V| + |E|})}$-Tiempo algoritmo para el problema de decisión NP-completo en el que se nos da un gráficoG=(V,E)yky queremos saber si hay una clique de tamaño≥k.$2^{\tilde O(\sqrt{|V| + |E|})}$$G=(V,E)$$k$$\geq k$

El algoritmo simplemente elimina todos los vértices de grado y los bordes incidentes sobre ellos, luego lo vuelve a hacer, y así sucesivamente, hasta que nos quedemos con un subgrafo inducido por vértices sobre un subconjunto V ' de vértices, cada uno de grado ≥ k , o con un gráfico vacío. En el último caso, sabemos que no puede existir una camarilla de tamaño ≥ k . En el primer caso, hacemos una búsqueda de fuerza bruta que se ejecuta en el tiempo aproximadamente | V ′ | k . Tenga en cuenta que | E | ≥ k ⋅ | V ′ | / 2 y k $< k$$V'$$\geq k$$\geq k$$|V'|^k$$|E| \geq k\cdot |V'| /2$, para que eso | E | ≥ k 2 / 2 , y así una búsqueda de fuerza bruta que se ejecuta en el tiempo | V ′ | k realmente se está ejecutando en el tiempo 2 O ( $k\leq |V'|$$|E| \geq k^2/2$$|V'|^k$.$2^{O(\sqrt{|E|} \cdot \log |V|)}$

Dado que cada gráfico plano en vértices tiene un ancho de árbol O ( $n$, todos los problemas que se pueden resolver en el tiempoO∗(2 O ( k ) )para gráficos de ancho de árbol como máximo ~k(hay MUCHOS de estos problemas) tienen algoritmos de tiempo subexponencial en gráficos planos calculando un factor constante aproximación al ancho de árbol en tiempo polinómico (por ejemplo, calculando el ancho de rama con el algoritmo ratcatcher) y luego ejecutando el algoritmo de ancho de árbol, lo que resulta en tiempos de ejecución de la formaO∗(2 O ( $O(\sqrt{n})$$O^*(2^{O(k)})$$k$para gráficos ennvértices. Los ejemplos son Conjunto Independiente Planar y Conjunto Dominador Planar, que son NP completos, por supuesto.$O^*(2^{O(\sqrt{n})})$$n$

There is a close connection between sub-exponential time solvability (SUBEPT) and fixed parameter tractability (FPT). The link between them is provided in the following paper.

An isomorphism between subexponential and parameterized complexity theory, Yijia Chen and Martin Grohe, 2006.

En resumen, introdujeron una noción llamada mapeo de miniaturización , que mapea un problema parametrizado en otro problema parametrizado ( Q , κ ) . Al ver un problema normal como un problema parametrizado por el tamaño de entrada, tenemos la siguiente conexión. (Ver el teorema 16 en el documento)$(P,\nu)$$(Q,\kappa)$

Teorema . está en SUBEPT si iff ( Q , κ ) está en FPT.$(P,\nu)$$(Q,\kappa)$

Tenga cuidado con las definiciones aquí. Normalmente vemos el problema -clique como parametrizado en k , por lo que no existe un algoritmo de tiempo sub-exponencial para asumir hipótesis de tiempo exponencial. Pero aquí dejamos que el problema se parametrice por el tamaño de entrada O ( m + n ) , por lo tanto, el problema se puede resolver en 2 O ( $k$$k$$O(m+n)$, que es un algoritmo de tiempo sub-exponencial. Y el teorema nos dice que elproblemak-clique es un parámetro fijo manejable bajo algún giro del parámetrok, lo cual es razonable.$2^{O(\sqrt{m}\log m)}$$k$$k$

En general, los problemas en SUBEPT bajo reducciones de SERF (familias de reducción sub-exponencial) pueden transformarse en problemas en FPT bajo reducciones de FPT. (Teorema 20 en el documento) Además, las conexiones son aún más fuertes ya que proporcionan un teorema de isomorfismo entre una jerarquía completa de problemas en la teoría de la complejidad exponencial del tiempo y la teoría de la complejidad parametrizada. (Teorema 25 y 47) Aunque el isomorfismo no está completo (faltan algunos enlaces entre ellos), todavía es bueno tener una idea clara de estos problemas, y podemos estudiar algoritmos de tiempo sub-exponenciales a través de la complejidad parametrizada.

Vea la encuesta realizada por Jörg Flum y Martin Grohe, junto con Jacobo Torán, el editor de la columna de complejidad, para obtener más información.

otro ejemplo puede ser el juego Cop and Robber, que es NP-hard pero solucionable en el tiempo en gráficos con n vértices. Registro bibliográfico BibTeX en XML Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Nicolas Nisse, Karol Suchan: persiguiendo a un ladrón rápido en un gráfico. Theor Comput Sci. 411 (7-9): 1167-1181 (2010)$2^{o(n)}$

$n/\text{polylog } n$$n$ is trivial).

There are hardness of approximation results under various hardness assumptions that don't quite match this, but still give hardness of $n^{1-o(1)}$. Personally, I believe that $n/\text{polylog } n$ approximation for clique is as good as polynomial-time algorithms would ever do.

But approximation of $n/\text{polylog } n$ for clique can easily be done in quasi-polynomial time.

An NP-hard problem is a problem that has a polynomial-time reduction from SAT. Even if SAT needs time $2^{\Omega(n)}$, this may translate to time $2^{\Omega(N^\epsilon)}$ for the problem we reduce to. If the latter has input size N, it may be the case that $N=n^{1/\epsilon}$ for a small constant $\epsilon$.