The Library
Fixed-parameter tractability of multicut in directed acyclic graphs
Tools
Tools
Tools
Kratsch, Stefan, Pilipczuk, Marcin, Pilipczuk, Michał and Wahlström, Magnus (2015) Fixed-parameter tractability of multicut in directed acyclic graphs. SIAM journal on discrete mathematics, Volume 29 (Number 1). pp. 122-144. doi:10.1137/120904202
|
PDF
WRAP_120904202.pdf - Published Version - Requires a PDF viewer. Download (735Kb) | Preview |
Official URL: http://dx.doi.org/10.1137/120904202
Abstract
The Multicut problem, given a graph G, a set of terminal pairs $\mathcal{T}=\{(s_i,t_i)\ |\ 1\leq i\leq r\}$, and an integer $p$, asks whether one can find a cutset consisting of at most $p$ nonterminal vertices that separates all the terminal pairs, i.e., after removing the cutset, $t_i$ is not reachable from $s_i$ for each $1\leq i\leq r$. The fixed-parameter tractability of Multicut in undirected graphs, parameterized by the size of the cutset only, has been recently proved by Marx and Razgon [SIAM J. Comput., 43 (2014), pp. 355--388] and, independently, by Bousquet, Daligault, and Thomassé [Proceedings of STOC, ACM, 2011, pp. 459--468], 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: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||
| Divisions: | Faculty of Science > Computer Science | ||||||||
| Library of Congress Subject Headings (LCSH): | Graph theory, Acyclic models, Computational complexity | ||||||||
| Journal or Publication Title: | SIAM journal on discrete mathematics | ||||||||
| Publisher: | Society for Industrial and Applied Mathematics | ||||||||
| ISSN: | 0895-4801 | ||||||||
| Official Date: | 15 January 2015 | ||||||||
| Dates: |
|
||||||||
| Volume: | Volume 29 | ||||||||
| Number: | Number 1 | ||||||||
| Number of Pages: | 23 | ||||||||
| Page Range: | pp. 122-144 | ||||||||
| DOI: | 10.1137/120904202 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Funder: | Nederlandse Organisatie voor Wetenschappelijk Onderzoek [Netherlands Organisation for Scientific Research] (NWO), Narodowe Centrum Nauki (NCN), Fundacja na rzecz Nauki Polskiej [Foundation for Polish Science] (FNP), European Research Council (ERC), Max-Planck-Gesellschaft zur Förderung der Wissenschaften [Max Planck Society for the Advancement of Science] | ||||||||
| Grant number: | N206567140 (NCN), 267959 (MRC) |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
