Advertisement
Published in:
2012 | OriginalPaper | Chapter
On Group Feedback Vertex Set Parameterized by the Size of the Cutset
Authors : Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk
Published in: Graph-Theoretic Concepts in Computer Science
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study parameterized complexity of a generalization of the classical
Feedback Vertex Set
problem, namely the
Group Feedback Vertex Set
problem: we are given a graph
G
with edges labeled with group elements, and the goal is to compute the smallest set of vertices that hits all cycles of
G
that evaluate to a non-null element of the group. This problem generalizes not only
Feedback Vertex Set
, but also
Subset Feedback Vertex Set
,
Multiway Cut
and
Odd Cycle Transversal
. Completing the results of Guillemot [Discr. Opt. 2011], we provide a fixed-parameter algorithm for the parameterization by the size of the cutset only. Our algorithm works even if the group is given as a blackbox performing group operations.