On group feedback vertex set parameterized by the size of the cutset

Details On group feedback vertex set parameterized by the size of the cutset On group feedback vertex set parameterized by the size of the cutset

2011-12-29

arxiv.org/abs/1112.6255v1

Computer Science

Data Structures and Algorithms

Scientific paper

We study the parameterized complexity of a robust 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 polynomial-time oracle.

Affiliated with

Also associated with

No associations

Rating

On group feedback vertex set parameterized by the size of the cutset does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On group feedback vertex set parameterized by the size of the cutset, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On group feedback vertex set parameterized by the size of the cutset will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-728394