The Library
Fixed-parameter tractability of multicut in directed acyclic graphs
Tools
Tools
Tools
Kratsch, Stefan, Pilipczuk, Marcin, Pilipczuk, Michał and Wahlström, Magnus (2012) Fixed-parameter tractability of multicut in directed acyclic graphs. In: Czumaj , Artur and Mehlhorn , Kurt and Pitts , Andrew and Wattenhofe, Roger , (eds.) Automata, Languages, and Programming : Proceedings, Part I of 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012. Lecture Notes in Computer Science, Volume 7391 . Berlin Heidelberg: Springer Verlag, pp. 581-593. ISBN 9783642315930
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1007/978-3-642-31594-7_49
Abstract
The Multicut problem, given a graph G, a set of terminal pairs \ensuremathT={(si,ti) | 1≤i≤r} and an integer p, asks whether one can find a cutset consisting of at most p non-terminal vertices that separates all the terminal pairs, i.e., after removing the cutset, t i is not reachable from s i for each 1 ≤ i ≤ r. The fixed-parameter tractability of Multicut in undirected graphs, parameterized by the size of the cutset only, has been recently proven by Marx and Razgon [2] and, independently, by Bousquet et al. [3], after resisting attacks as a long-standing open problem. In this paper we prove that Multicut is fixed-parameter tractable on directed acyclic graphs, when parameterized both by the size of the cutset and the number of terminal pairs. We complement this result by showing that this is implausible for parameterization by the size of the cutset only, as this version of the problem remains W[1]-hard.
| Item Type: | Book Item | ||||
|---|---|---|---|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Series Name: | Lecture Notes in Computer Science | ||||
| Publisher: | Springer Verlag | ||||
| Place of Publication: | Berlin Heidelberg | ||||
| ISBN: | 9783642315930 | ||||
| ISSN: | 0302-9743 | ||||
| Book Title: | Automata, Languages, and Programming : Proceedings, Part I of 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012 | ||||
| Editor: | Czumaj , Artur and Mehlhorn , Kurt and Pitts , Andrew and Wattenhofe, Roger | ||||
| Official Date: | 2012 | ||||
| Dates: |
|
||||
| Volume: | Volume 7391 | ||||
| Page Range: | pp. 581-593 | ||||
| DOI: | 10.1007/978-3-642-31594-7_49 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
