Vantagens algorítmicas da largura do caminho sobre a largura da árvore

A largura da árvore desempenha um papel importante nos algoritmos do FPT, em parte porque muitos problemas são parametrizados pelo FPT pela largura da árvore. Uma noção relacionada, mais restrita, é a de largura de caminho. Se um gráfico tem largura de caminho , ele também tem largura de árvore no máximo , enquanto na direção inversa, a largura de árvore implica apenas largura de caminho na maioria dos e isso é apertado. $k$ $k$ $k$ $k\log n$

Diante do exposto, pode-se esperar que possa haver uma vantagem algorítmica significativa para gráficos de largura de caminho limitada. No entanto, parece que a maioria dos problemas que são FPT para um parâmetro são FPT para o outro. Estou curioso para saber de quaisquer contra-exemplos disso, ou seja, problemas que são "fáceis" para a largura do caminho, mas "difíceis" para a largura da árvore.

Permitam-me mencionar que fiquei motivado a fazer esta pergunta, encontrando um artigo recente de Igor Razgon ("Sobre OBDDs para CNFs de largura de árvore limitada", KR'14), que deu um exemplo de um problema com solução quando é a largura do caminho e um limite inferior (aproximadamente) quando é a largura da árvore. Gostaria de saber se existem outros espécimes com esse comportamento. $2^{k}n$ $k$ $n^k$ $k$

Resumo: Existem exemplos de problemas naturais que são W-hard parametrizados por largura de árvore, mas FPT parametrizado por largura de caminho? Mais amplamente, existem exemplos de problemas cuja complexidade é conhecida / acredita-se ser muito melhor quando parametrizada pela largura do caminho em vez da largura da árvore?

parameterized-complexity treewidth graph-minor Michael Lampis
fonte

Existem problemas fáceis nos caminhos, mas NP-Hard nas árvores. Isso inclui multicut mínimo e multiflow máximo máximo.

Chandra Chekuri

@ChandraChekuri Esse é um bom argumento, mas os algoritmos para caminhos para esses problemas geralmente se generalizam em largura de caminho? Por exemplo, para o máximo máximo múltiplo inteiro, acho que não é esse o caso. Garg, Vazirani e Yannakakis provaram a dureza NP para árvores em "Algoritmos de aproximação dual-prima para fluxo integral e multicut em árvores". A redução lá usa uma árvore de altura 3. Isso significa que o problema é difícil de NP para uma largura de caminho constante.

Michael Lampis

Novamente, essa não é uma resposta clara à pergunta original. Sabe-se que a folga de corte de fluxo nos gráficos de largura de caminho k é delimitada por f (k) para alguma função f via resultado de Lee e Sidiropoulos. É um importante problema em aberto se esse resultado vale para a largura da árvore. O caso k = 3 está aberto para a largura da árvore.

Chandra Chekuri

O melhor algoritmo para o ciclo hamiltoniano parametrizado por largura de caminho possui tempo de execução ( arxiv.org/abs/1211.1506 ) enquanto o melhor algoritmo de largura de árvore é ( arxiv.org/abs /1103.0534 ) No entanto, provavelmente é apenas uma lacuna aguardando para ser fechada.

(2 + \sqrt{2})^{p w}

$(2+\sqrt{2})^{pw}$

4^{t w}

$4^{tw}$

Daniello

É mostrado que [1] o Problema Misto do Carteiro Chinês (MCPP) parametrizado pela largura do caminho é -hard, mesmo se todas as arestas e arcos do gráfico de entrada tiverem peso e for FPT em relação à profundidade da árvore. Este é o primeiro problema que sabemos que foi mostrado duro em relação à largura da árvore, mas FPT em relação à largura da árvore. Observe que a largura do caminho de um gráfico está entre a largura da árvore e a largura da árvore. $W[1]$ $G$ $1$ $W[1]$

O problema do Steiner Multicut, que solicita, dado um gráfico não direcionado , uma coleção , , de conjuntos terminais de tamanho no máximo e um número inteiro , se existe um conjunto com no máximo arestas ou nós, de modo que, para cada conjunto pelo menos um par de terminais é em diferentes componentes ligados de . $G$ $T = \{T_1, . . . , T_t\}$ $T_i ⊆ V(G)$ $p$ $k$ $S$ $k$ $T_i$ $G \ S$

Nó Steiner Multicut, Edge Steiner Multicut e Restr. O nó Steiner Multicut é -hard para o parâmetro , mesmo que e [2]. $W[1]$ $k$ $p = 3$ $tw(G) = 2$

[1] https://core.ac.uk/download/pdf/77298274.pdf.

[2] http://drops.dagstuhl.de/opus/volltexte/2015/4911/pdf/11.pdf.

Rupei Xu
fonte

Vantagens algorítmicas da largura do caminho sobre a largura da árvore

Respostas: