The Library
On group feedback Vertex Set parameterized by the size of the cutset
Tools
Tools
Tools
Cygan, Marek, Pilipczuk, Marcin and Pilipczuk, Michał (2016) On group feedback Vertex Set parameterized by the size of the cutset. Algorithmica, 74 (2). pp. 630-642. doi:10.1007/s00453-014-9966-5 ISSN 0178-4617.
|
PDF
WRAP_1371795-cs-270115-group-fvs.pdf - Accepted Version - Requires a PDF viewer. Download (394Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/s00453-014-9966-5
Abstract
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 (Discrete Optim 8(1):61–71, 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.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
| Library of Congress Subject Headings (LCSH): | Computational complexity, Vertex operator algebras | ||||||||
| Journal or Publication Title: | Algorithmica | ||||||||
| Publisher: | Springer Verlag | ||||||||
| ISSN: | 0178-4617 | ||||||||
| Official Date: | February 2016 | ||||||||
| Dates: |
|
||||||||
| Volume: | 74 | ||||||||
| Number: | 2 | ||||||||
| Page Range: | pp. 630-642 | ||||||||
| DOI: | 10.1007/s00453-014-9966-5 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Date of first compliant deposit: | 28 December 2015 | ||||||||
| Date of first compliant Open Access: | 28 December 2015 | ||||||||
| Funder: | Narodowe Centrum Nauki (NCN), Fundacja na rzecz Nauki Polskiej [Foundation for Polish Science] (FNP), European Research Council (ERC), Seventh Framework Programme (European Commission) (FP7) | ||||||||
| Grant number: | N206567140 (NCN), 267959 (MRC) | ||||||||
| Embodied As: | 1 |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
