Parametrização dupla não-padrão de problemas gráficos

8

Um resultado fundamental na complexidade parametrizada dos problemas gráficos é que VERTEX COVER parametrizado pelo tamanho da solução é um parâmetro fixo-tratável (FPT). Por outro lado, quando parametrizado pelo "parâmetro duplo" , torna-se equivalente a INDEPENDENT SET parametrizado pelo tamanho da solução (porque qualquer cobertura de vértice é o complemento de um conjunto independente) e, portanto, é W [1] -hard. $k$ $|V(G)|-k$

Embora isso pareça menos natural, estou interessado na complexidade parametrizada do VERTEX COVER para o parâmetro . Este é um parâmetro maior que . O VERTEX COVER FPT é para este parâmetro? $|E(G)|-k$ $|V(G)|-k$

Nota: Também estou interessado em parametrizações semelhantes para outros problemas de gráfico (por exemplo, DOMINATING SET). O único lugar onde vi os dois tipos de parâmetros duplos estudados é para o problema do hipergrama TEST COVER no artigo de 2012 " Estudo parametrizado do problema da tampa do teste ", de Crowston, Gutin, Jones, Saurabh e Yeo. (também no arXiv )

Edit (12/04/2016): Esta parametrização também é estudada para o outro problema do hipergráfico HITTING SET no artigo de 2011 Kernels para parametrizações abaixo do limite superior do conjunto de batidas e problemas de conjuntos dominantes direcionados por Gutin, Mones e Yeo ( arXiv link ).

reference-request graph-algorithms fixed-parameter-tractable Florent Foucaud
fonte

5

Sejae. O parâmetro duplo é sempre pelo menos tão grande quanto que por sua vez é pelo menos o tamanho de um conjunto de arestas de realimentação, um conjunto de arestas cuja remoção torna acíclico. $n:=|V(G)|$ $m:= |E(G)|$ $m-k$ $m-n$ $G$

O tamanho de um menor conjunto de arestas de feedback, vamos chamá-lo de número da aresta de feedback , também é pelo menos tão grande quanto o número do vértice de feedback e a largura de árvore do gráfico. Isso implica diretamente que a Vertex Cover é um parâmetro fixo tratável para . Além disso, ele possui um núcleo polinomial, já que o Vertex Cover, parametrizado pelo número do vértice de feedback, possui um (isso foi mostrado por Jansen e Bodlaender em Vertex Cover Kernelization Revisited - Limites superior e inferior para um parâmetro refinado. Theory Comput. 263-299 (2013), http://dx.doi.org/10.1007/s00224-012-9393-4 ). $\phi$ $m-k$

Um kernel linear direto simples para a cobertura de vértice parametrizado pelo número da aresta de retorno deve ser obtido da seguinte maneira: Remova todos os vértices de grau 0, adicione o vizinho de qualquer vértice de grau 1 à cobertura de vértice e reduza os caminhos dos vértices de grau 2 que contenham pelo menos 2 vértices (diminuindo o limite em acordo). Após aplicação exaustiva dessas regras de redução, no gráfico resultante . Isso implica diretamente em um kernel para o parâmetro maior . $\phi$ $k$ $n=O(\phi)$ $m-k$

Para responder à sua pergunta para obter referências: Eu procuraria o número da borda de feedback menor que o parâmetro duplo , foi considerado na literatura e geralmente fornece resultados de rastreabilidade de parâmetro fixo também para Dominating Set (como o parâmetro é bastante grande) . Aqui estão três exemplos adicionais: $m-k$

Johannes Uhlmann, Mathias Weller: Planarização de duas camadas parametrizada pelo conjunto de arestas de feedback. Theor. Comput. Sci. 494: 99-111 (2013), http://dx.doi.org/10.1016/j.tcs.2013.01.029

André Nichterlein, Rolf Niedermeier, Johannes Uhlmann, Mathias Weller: Em casos tratáveis de seleção de conjuntos de alvos. Rede social. Analys. Mining 3 (2): 233-256 (2013), http://dx.doi.org/10.1007/s13278-012-0067-7

Sepp Hartung, Christian Komusiewicz, André Nichterlein: Algoritmia parametrizada e experimentos computacionais para encontrar 2 clubes. J. Algoritmos de gráfico Appl. 19 (1): 155-190 (2015), http://dx.doi.org/10.7155/jgaa.00352

C Komus
fonte

Se houver, "Remover todos os vértices de grau 0" diminui n sem alterar m, portanto aumenta mn. Por conseguinte, o tamanho do gráfico resultante sendo linear no parâmetro do gráfico resultante não significa que o tamanho do gráfico resultante tenha qualquer limite em termos do parâmetro do gráfico de entrada .

Sim, obrigado por apontar isso. Alterei esta parte para uma kernelização para o número da borda de feedback menor.

C KOMUS

2

Pergunta subsidiária: os 2 artigos que apontei eram para problemas de hipergrafo, mas não é necessário maior que pois pode haver menos hipervedades que vértices. Existe algum truque genérico que funcione lá?

m - k

$m-k$

n - k

$n-k$

Florent Foucaud

9

Eu acho que esse problema é FPT. Suponha que o gráfico contenha um caminho nos vértices . Então, afirmo que a resposta é SIM: selecionamos o segundo, quarto, sexto etc. vértices desse caminho em uma solução e os removemos do gráfico. Agora temos um gráfico com . É fácil encontrar uma cobertura de vértice de com tamanho máximo. Juntamente com os vértices removidos isto dá uma cobertura de vértices de tamanho no máximo para . $2k+1$ $G'$ $|E(G')|\le |E(G)|-2k$ $G'$ $|E(G')|$ $|E(G)|-k$ $G$

Se o gráfico não contiver um caminho nos vértices , uma árvore DFS do gráfico terá altura no máximo e, portanto, poderá ser usada para construir uma decomposição de árvore com largura no máximo . Podemos então resolver a Vertex Cover de maneira otimizada com o algoritmo padrão para largura de árvore. $2k+1$ $2k+1$ $2k$

Michael Lampis
fonte

Obrigado, legal! Se você conhece uma referência onde esse parâmetro é estudado (para outros problemas de gráfico), entre em contato.

Florent Foucaud

Parametrização dupla não-padrão de problemas gráficos

Respostas: