Fixed-parameter tractability of multicut in directed acyclic graphs

Details Fixed-parameter tractability of multicut in directed acyclic graphs Fixed-parameter tractability of multicut in directed acyclic graphs

2012-02-26

arxiv.org/abs/1202.5749v1

Computer Science

Data Structures and Algorithms

Scientific paper

The MULTICUT problem, given a graph G, a set of terminal pairs T={(s_i,t_i) | 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 (STOC'11) and, independently, by Bousquet et al. (STOC'11), 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.

Affiliated with

Also associated with

No associations

Rating

Fixed-parameter tractability of multicut in directed acyclic graphs 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 Fixed-parameter tractability of multicut in directed acyclic graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fixed-parameter tractability of multicut in directed acyclic graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-216007