Parametrisierte Komplexität des Zählens von Bicliques

9

In einer früheren Frage habe ich nach dem parametrisierten Algorithmus zum Auffinden von Bicliques gefragt, ob es schnelle parametrisierte Algorithmen zum Auffinden eines Biclique in einem Vertex-Graphen gibt, und festgestellt, dass er offen ist, wenn es sich um FPT wrt . Gilt das auch für das Zählen der Bicliques, oder ist bekannt, dass dies # -hard wrt (oder ein anderer Begriff von Härte)?k×kknkW \ [ 1 \] kk×kW\[1\]k

Ich weiß, dass das Zählen von induzierten Bicliques # -hart ist, was eine einfache Reduktion zum Auffinden eines induzierten Biclique in Abschnitt 4.5 in der These von Serge Gaspers erweitert .W \ [ 1 \]k×kW\[1\]

Andreas Björklund
quelle

Antworten:

9

Dies sollte nach einem Standardinterpolationsargument #W [1] -hart sein. Hier ist eine grobe Skizze.

Betrachten Sie zunächst die mehrfarbige Version des Biclique-Problems: Wenn ein Diagramm vorliegt, dessen Scheitelpunktsatz in die Klassen , finden Sie einen Biclique, der genau einen Scheitelpunkt aus jedem Satz enthält. Im Gegensatz zu Biclique, dessen FPT-Status offen ist, ist diese mehrfarbige Version als W [1] -hart bekannt: Es gibt eine einfache Reduktion von Clique. Ich glaube, es sollte auch #W [1] -hart sein.X1,,X2k

Wenn ein Graph und eine Partition wie oben gegeben sind, erhalten wir einen neuen Graphen G ', indem wir jeden Scheitelpunkt von X i durch einen unabhängigen Satz der Größe x i ersetzen (und jede Kante zwischen X i und X j durch x i × x j ersetzen biclique). Nun ist die Anzahl der k × k- Bikliken in G ' eine Funktion der 2 k- Variablen x 1 , , x 2 kGGX.ichxichX.ichX.jxich×xjk×kG'2kx1,,x2k. Siehe In der Tat kann man , daß diese Funktion ein Polynom vom Grad höchstens und der Koeffizient des Ausdrucks x 1x 2 k ist genau die Anzahl der mehrfarbigen bicliques in G . Indem wir also ausreichend viele Wertekombinationen in die Variablen x i einsetzen und die Anzahl der Bikliken in G 'zählen , können wir dieses Polynom an ausreichend vielen Stellen auswerten, um seine Koeffizienten durch Interpolation wiederherzustellen.2kx1x2kGxichG'

Daniel Marx
quelle
Danke Daniel, das macht vollkommen Sinn! Ich habe auch gerade herausgefunden, dass Marc Thurley es beweist #A [1] -hard crm.cat/mthurley/theses/diploma.pdf
Andreas Björklund
Und die sparsame Reduktion von Clique zu mehrfarbigem k × k- Biclique ist in Anhang B auf pages.cs.wisc.edu/~holger/papers/dm12soda.pdfkk×k
Andreas Björklund