Nicht standardmäßige doppelte Parametrisierung von Diagrammproblemen

8

Ein grundlegendes Ergebnis der parametrisierten Komplexität von Graphproblemen ist, dass der durch die Lösungsgröße parametrisierte VERTEX COVER festparametrisch (FPT) ist. Wenn es andererseits durch den "Doppelparameter" parametrisiert wird, wird es äquivalent zu INDEPENDENT SET, das durch die Lösungsgröße parametrisiert wird (weil jede Scheitelpunktabdeckung das Komplement einer unabhängigen Menge ist), und ist es somit W [1] -hart. $k$ $|V(G)|-k$

Obwohl dies weniger natürlich erscheint, interessiert mich die parametrisierte Komplexität von VERTEX COVER für den Parameter . Dies ist ein größerer Parameter als . Ist VERTEX COVER FPT für diesen Parameter? $|E(G)|-k$ $|V(G)|-k$

Hinweis: Ich interessiere mich auch für ähnliche Parametrisierungen für andere Diagrammprobleme (z. B. DOMINATING SET). Der einzige Ort, an dem ich beide Arten von Doppelparametern untersucht habe, ist das Hypergraph- Problem TEST COVER in der 2012 erschienenen Veröffentlichung " Parametrisierte Untersuchung des Testdeckungsproblems" von Crowston, Gutin, Jones, Saurabh und Yeo. (auch auf arXiv )

Edit (04/12/2016): Diese Parametrisierung wird auch für das andere Hypergraph-Problem HITTING SET in der 2011 erschienenen Arbeit Kernels für Parametrisierungen der Schlagmenge und der gerichteten dominierenden Mengenprobleme von Gutin, Mones und Yeo ( arXiv) untersucht Link ).

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

5

Seiund. Der Doppelparameter ist immer mindestens so groß wie was wiederum mindestens so groß ist wie die Größe eines Rückkopplungskantensatzes, eines Satzes von Kanten, dessen Entfernung azyklisch macht . $n:=|V(G)|$ $m:= |E(G)|$ $m-k$ $m-n$ $G$

Die Größe eines kleinsten Rückkopplungskantensatzes, nennen wir ihn Rückkopplungskantennummer , ist ebenfalls mindestens so groß wie die Rückkopplungsscheitelpunktnummer und die Baumbreite des Diagramms. Dies impliziert direkt, dass Vertex Cover für festen Parametern nachvollziehbar ist . Darüber hinaus hat es einen Polynomkern, da die durch die Rückkopplungs-Vertexnummer parametrisierte Vertex-Abdeckung eine hat (dies wurde von Jansen und Bodlaender in Vertex-Cover-Kernelisierung überarbeitet - Ober- und Untergrenze für einen verfeinerten Parameter gezeigt. Theory Comput. Syst. 53 (2): 263-299 (2013), http://dx.doi.org/10.1007/s00224-012-9393-4 ). $\phi$ $m-k$

Ein einfacher direkter linearer Kernel für die Scheitelpunktabdeckung, der durch die Rückkopplungskantennummer parametrisiert ist, sollte wie folgt erhältlich sein: Entfernen Sie alle Scheitelpunkte vom Grad 0, fügen Sie den Nachbarn eines Scheitelpunkts vom Grad 1 zur Scheitelpunktabdeckung hinzu und reduzieren Sie die Pfade der Scheitelpunkte vom Grad 2, die mindestens 2 Eckpunkte enthalten (die Grenze für entsprechend verringern ). Nach erschöpfender Anwendung dieser Reduktionsregeln ist im resultierenden Graphen . Dies impliziert direkt einen Kernel für den größeren Parameter . $\phi$ $k$ $n=O(\phi)$ $m-k$

Um Ihre Frage als Referenz zu beantworten: Ich würde nach einer Rückkopplungskantenzahl suchen, die kleiner als der Doppelparameter ist, in der Literatur berücksichtigt wurde und häufig Ergebnisse für die Traktabilität fester Parameter auch für Dominating Set liefert (da der Parameter recht ist) groß). Hier sind drei weitere Beispiele: $m-k$

Johannes Uhlmann, Mathias Weller: Zweischichtige Planarisierung, parametrisiert durch Rückkopplungskantensatz. 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: Über nachvollziehbare Fälle der Zielsatzauswahl. Soziales Netzwerk. Analys. Mining 3 (2): 233-256 (2013), http://dx.doi.org/10.1007/s13278-012-0067-7

Sepp Hartung, Christian Komusiewicz, André Nichterlein: Parametrisierte Algorithmen und Computerexperimente zur Suche nach 2-Clubs. J. Graph Algorithms Appl. 19 (1): 155-190 (2015), http://dx.doi.org/10.7155/jgaa.00352

C Komus
quelle

Wenn es welche gibt, verringert "Alle Scheitelpunkte vom Grad 0 entfernen" n, ohne m zu ändern, und erhöht so mn. Dementsprechend bedeutet die Größe des resultierenden Graphen, die im Parameter des resultierenden Graphen linear ist, nicht, dass die Größe des resultierenden Graphen hinsichtlich des Parameters des Eingabegraphen begrenzt ist.

Ja, danke, dass Sie darauf hingewiesen haben. Ich habe diesen Teil in eine Kernelisierung für die Rückkopplungskantennummer geändert, die kleiner ist.

C Komus

2

m - k

$m-k$

n - k

$n-k$

9

$2k+1$ $G'$ $|E(G')|\le |E(G)|-2k$ $G'$ $|E(G')|$ $|E(G)|-k$ $G$

$2k+1$ $2k+1$ $2k$

Michael Lampis
quelle

Danke, ordentlich! Wenn Sie eine Referenz kennen, in der solche Parameter untersucht werden (für andere Diagrammprobleme), lassen Sie es mich bitte wissen.

Florent Foucaud

Nicht standardmäßige doppelte Parametrisierung von Diagrammproblemen

Antworten: