Problemas de gráfico rígido subexponencialmente solucionáveis

25

À luz do resultado recente de Arora, Barak e Steurer, Algoritmos Subexponenciais para Jogos Exclusivos e Problemas Relacionados , estou interessado em problemas gráficos que têm algoritmos de tempo subexponenciais, mas que não são polinomialmente solucionáveis. Um exemplo é famoso isomorfismo gráfico que tem algoritmo subexponencial de $2^{O(n^{1/2} \log n)}$ de tempo de execução. Outro exemplo é o problema log-Clique, que é solucionável em tempo quase-polinomial ( ). $n^{O(\log n)}$

Estou procurando exemplos interessantes e, de preferência, uma referência a pesquisas de problemas subexponenciais de grafos rígidos (não necessariamente completos). Além disso, há algum gráfico com completo com algoritmos de tempo subexponenciais? $NP$ $NP$

Impagliazzo, Paturi e Zane mostraram que a Hipótese de Tempo Exponencial implica que Clique, k-Colorability e Vertex Cover precisam de tempo. $2^{\Omega(n)}$

cc.complexity-theory reference-request Mohammad Al-Turkistany
fonte

2

Apenas para completar: log-CLIQUE =

{(G, k) | G has n vertices, k = \log n and G has a clique of size k}

$\{(G, k) | G \text{ has }n\text{ vertices, }k = \log n\text{ and }G\text{ has a clique of size }k\}$

MS Dousti

20

A propósito, o problema de Max Clique, em geral generalizada, pode ser resolvido no tempo ondeé o tamanho da entrada. $2^{\tilde O(\sqrt N)}$ $N$

Isso é trivial se o gráfico for representado por meio de uma matriz de adjacência, porque , e uma busca por força bruta levará tempo . $N=|V|^2$ $2^{O(|V|)}$

Mas podemos obter o mesmo limite, mesmo que o gráfico seja representado por listas de adjacências, através de um algoritmo de tempo de execução . Para ver como, vamos obter um $2^{\tilde O(\sqrt{|V| + |E|})}$ -Tempo algoritmo para o problema de decisão NP-completos em que nos é dado um grafoee queremos saber se há um clique de tamanho. $2^{\tilde O(\sqrt{|V| + |E|})}$ $G=(V,E)$ $k$ $\geq k$

O algoritmo simplesmente remove todos os vértices de grau e as arestas incidentes sobre eles, e o faz novamente, e assim por diante, até ficarmos com um subgrafo induzido por vértice sobre um subconjunto de vértices, cada um com grau , ou com um gráfico vazio. No último caso, sabemos que nenhuma panelinha de tamanho pode existir. No primeiro caso, fazemos uma busca por força bruta no tempo aproximadamente . Note que e $< k$ $V'$ $\geq k$ $\geq k$ $|V'|^k$ $|E| \geq k\cdot |V'| /2$ , para que , e assim por uma pesquisa de força bruta em execução no tempo está realmente rodando no tempo $k\leq |V'|$ $|E| \geq k^2/2$ $|V'|^k$ . $2^{O(\sqrt{|E|} \cdot \log |V|)}$

Luca Trevisan
fonte

12

De fato, para esses tipos de razões Impagliazzo, Camas e Zane argumentou que quando perguntando sobre

vs

a complexidade você precisa definir

para ser o tamanho da testemunha (que você precisa definir como parte de o problema). No caso da classe

, a testemunha é do tamanho

2^{Ω (n)}

$2^{\Omega(n)}$

2^{o (n)}

$2^{o(n)}$

n

$n$

k

$k$

para pequenas

, enquanto que, como você diz, você pode assumir WLOG há pelo menos

bordas e o tamanho da entrada é muito maior que o tamanho da testemunha.

\log (\binom{| V |}{k}) \sim k \log | V |

$\log \binom{|V|}{k} \sim k\log |V|$

k

$k$

k | V |

$k|V|$

Boaz Barak

22

Como todo gráfico planar em vértices possui uma largura de árvore $n$ , todos os problemas solucionáveis no tempo depara gráficos de largura de árvore no máximo ~(existem muitos desses problemas) possuem algoritmos de tempo subexponencial em gráficos planares, calculando um fator constante aproximação para o treewidth em tempo polinomial (por exemplo, calculando a branchwidth com o algoritmo ratcatcher) e, em seguida, executar o algoritmo treewidth, resultando em tempos de execução da forma $O(\sqrt{n})$ $O^*(2^{O(k)})$ $k$ para gráficos emvértices. Exemplos são: Conjunto Independente Planar e Conjunto Dominante Planar, que são NP-completos, é claro. $O^*(2^{O(\sqrt{n})})$ $n$

Bart Jansen
fonte

15

Existe uma conexão estreita entre a solvabilidade de tempo subexponencial (SUBEPT) e a rastreabilidade de parâmetro fixo (FPT). O link entre eles é fornecido no documento a seguir.

Um isomorfismo entre a teoria da complexidade subexponencial e parametrizada , Yijia Chen e Martin Grohe, 2006.

Em resumo, eles introduziram uma noção chamada mapeamento de miniaturização , que mapeia um problema parametrizado para outro problema parametrizado $(P,\nu)$ . Ao visualizar um problema normal como um problema parametrizado pelo tamanho da entrada, temos a seguinte conexão. (Veja o teorema 16 no artigo) $(Q,\kappa)$

Teorema . está em SUBEPT se f estiver em FPT. $(P,\nu)$ $(Q,\kappa)$

Tenha cuidado com as definições aqui. Normalmente, vemos o problema da classe como parametrizado em ; portanto, não há algoritmo de tempo subexponencial para assumir a hipótese de tempo exponencial. Mas aqui deixamos o problema ser parametrizado pelo tamanho de entrada , assim o problema pode ser resolvido em $k$ $k$ $O(m+n)$ , que é um algoritmo de tempo subexponencial. E o teorema nos diz que oproblema da classeé um parâmetro fixo tratável sob alguma torção do parâmetro, o que é razoável. $2^{O(\sqrt{m}\log m)}$ $k$ $k$

Em geral, problemas no SUBEPT sob reduções do SERF (famílias de redução subexponencial) podem ser transformados em problemas no FPT sob reduções do FPT. (Teorema 20 no artigo) Além disso, as conexões são ainda mais fortes, pois fornecem um teorema de isomorfismo entre toda uma hierarquia de problemas na teoria da complexidade do tempo exponencial e na teoria da complexidade parametrizada. (Teorema 25 e 47) Embora o isomorfismo não esteja completo (há alguns links ausentes entre eles), ainda é bom ter uma imagem clara sobre esses problemas, e podemos estudar algoritmos de tempo subexponenciais via complexidade parametrizada.

Veja a pesquisa de Jörg Flum e Martin Grohe, juntamente com Jacobo Torán, editor da coluna de complexidade, para mais informações.

Hsien-Chih Chang 張顯之
fonte

Sim. aliás, Flum e Grohe escreveram a pesquisa; Toran é o editor de colunas de complexidade.

Andy Drucker

@ Andy: Obrigado pela correção. Vou modificar o artigo de acordo.

Hsien-Chih Chang,

12

outro exemplo pode ser o jogo Cop and Robber, que é NP-difícil, mas solucionável no tempo em gráficos com n vértices. Registro bibliográfico do BibTeX em XML Fedor V. Fomin, Petr A. Golovach, Jan Kratochvíl, Nicolas Nisse, Karol Suchan: Perseguindo um ladrão rápido em um gráfico. Theor. Comput. Sci. 411 (7-9): 1167-1181 (2010) $2^{o(n)}$

XXYYXX
fonte

3

N P

$\mathsf{NP}$

6

N P

$NP$

L \in N P T I M E (n^{k})

$L \in NPTIME(n^k)$ , and then form a 'padded' version

L^{'}

$L'$ in which the 'yes' instances are of form

(x, 1^{| x |^{c}})

$(x, 1^{|x|^c})$ , with

x \in L

$x \in L$ , for some fixed

c > k

$c > k$ . Then

L^{'}

$L'$ is

N P

$NP$ , but has a deterministic algorithm running in time essentially

2^{n^{k / c}}

$2^{n^{k/c}}$ .

Andy Drucker

7

The best approximation algorithm for clique gives an unbelievably bad approximation factor $n/\text{polylog } n$ (recall that approximation factor of $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$ .

Dana Moshkovitz
fonte

Problemas de gráfico rígido subexponencialmente solucionáveis

Respostas: