Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
PDF
WRAP_120904202.pdf - Published Version - Requires a PDF viewer.

Download (735Kb) | Preview
Official URL: http://dx.doi.org/10.1137/120904202

Request Changes to record.

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:
DateEvent
15 January 2015Published
21 October 2014Accepted
2 January 2013Submitted
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 View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us