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

18

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 k , enquanto na direção inversa, a largura de árvore k implica apenas largura de caminho na maioria dos k \ log n e isso é apertado.kk k log nkkklogn

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.k n k k2knknkk

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?

Michael Lampis
fonte
7
Existem problemas fáceis nos caminhos, mas NP-Hard nas árvores. Isso inclui multicut mínimo e multiflow máximo máximo.
Chandra Chekuri
2
@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
3
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. 4 t w(2+2)pw4tw
Daniello

Respostas:

5

É 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.G 1 W [ 1 ]W[1]G1W[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 .T = { T 1 , . . . , T t } t iV ( G ) p K S K T I L SGT={T1,...,Tt}TiV(G)pkSkTiG S

Nó Steiner Multicut, Edge Steiner Multicut e Restr. O nó Steiner Multicut é -hard para o parâmetro , mesmo que e [2].k p = 3 t w ( G ) = 2W[1]kp=3tw(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