FPT Algorithms for Connected Feedback Vertex Set

Misra, Neeldhara; Philip, Geevarghese; Raman, Venkatesh; Saurabh, Saket; Sikdar, Somnath

doi:10.1007/978-3-642-11440-3_25

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

会議論文

FPT Algorithms for Connected Feedback Vertex Set

MPS-Authors

There are no MPG-Authors in the publication available

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

Misra, N., Philip, G., Raman, V., Saurabh, S., & Sikdar, S. (2010). FPT Algorithms for Connected Feedback Vertex Set. In M. S., Rahman, & S., Fujita (Eds.), WALCOM: Algorithms and Computation (pp. 269-280). Berlin: Springer. doi:10.1007/978-3-642-11440-3_25.

引用: https://hdl.handle.net/11858/00-001M-0000-0019-DC05-8

要旨

We study the recently introduced \textscConnected Feedback Vertex Set (CFVS)} problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical \textsc{Feedback Vertex Set} problem and is defined as follows: given a graph G=(V,E) and an integer k, decide whether there exists F\subseteq V, |F| ≤q k, such that G[V \setminus F] is a forest and G[F] is connected. We show that \textsc{Connected Feedback Vertex Set} can be solved in time O(2^{O(k)}n^{O(1)}) on general graphs and in time O(2^{O(\sqrt{k}\log k)}n^{O(1)}) on graphs excluding a fixed graph H as a minor. Our result on general undirected graphs uses, as a subroutine, a parameterized algorithm for \textsc{Group Steiner Tree}, a well studied variant of \textsc{Steiner Tree}. We find the algorithm for \textsc{Group Steiner Tree of independent interest and believe that it could be useful for obtaining parameterized algorithms for other connectivity problems.