d-Path Vertex Cover

Dnes mluvil Radovan na téma d-PVC a hitting set.

Hitting set

vstup: je dán graf a nějaké podmnožiny V(G) F, kde každé je velké nejvýše d.
výstup: vybrat co nejméně vrcholů takových, aby bylo pokryté každé F.

d-Path Vertex Cover

vstup: graf G, $k \in \mathbb{Z}_0^+$, kde $k$ je velikost řešení
výstup: $F \subseteq V(G), |F| \leq k$
tedy G \ F takový, aby neobsahoval cestu na d vrcholech

Je to jako hitting set, kde tím hitting setem jsou všechny cesty délky d.

Známé výsledky

  • 3-PVC - 1.745^k
  • 4-PVC - 3^k
  • 5-PVC - 4^k

Řešení 3 a 4 je typicky založené na branch and reduce. Nedá se moc zobecnit, závisí na d.
Existuje ještě 2^k na 3-PVC založené na iterativní kompresi.

Iterativní komprese

Příklad: d-PVC s $P_d$ free bipartizací

vstup: graf G, $k \in \mathbb{Z}^+, V_1, V_2$, kde $V_1 \cup V_2 = G$, $V_1$ a $V_2$ neobsahuje $P_d$, $V_1 \cap V_2 = \emptyset$ výstup: $F \subseteq V_2, |F| \leq k$

Postup

Začneme s prázdným grafem G’ a prázdným řešením F. Postupně přidávám vrcholy grafu G do grafu G’ a do řešení F, dokud jich nemám k. Jakmile přidávám (k+1)., tak musím najít řešení. Jestli jsem ho nenašel, tak jsem našel optimum.

Podrobněji kompresní rutina

Mám v ruce F a G’. Rozdělím si dočasný výsledek na 2 množiny X a Y, X chceme nechat v řešení a Y chceme vyměnit. X rovnou odebereme z grafu, protože to stejně uděláme. Takže:

  1. Vyrobíme G” = G’ \ X.
  2. Pokud Y obsahuje P_d, continue, jinak hledej řešení disjunktní s Y.

X a Y se zkusí všechny. Dá se ukázat, že to základ exponenciály nezvýší o víc než 1.

Open problems

  • Ukažte, že d-PVC lze řešit $(d - 1)^k$?
  • Kernely pro tyhle problémy. Pro d-hitting set se umí hledat k^d kernel. Kdyby se umělo obecně (k)^(d-\eps), tak se budou dít špatné věci (coNP = NP poly). Pro 3-PVC existuje lineární kernel (asi 5).
  • Jednodušší algoritmus pro 5-PVC, existující je moc dlouhý.

Repete hitting setu

d-hitting set se dá řešít v nějakém (d-1 + O(1/d))^k založené na zakazování vrcholu, pokud jsem ho po vyzkoušení do žádného výsledku nepřidal. Tohle se nedá dělat pro d-PVC, ale jde pro d-PVC s P_d free bipartizací.