Fixed‐parameter tractability and data reduction for multicut in trees
Authors:
Abstract
We study an NP‐complete (and MaxSNP‐hard) communication problem on tree networks, the so‐called MULTICUT IN TREES: given an undirected tree and some pairs of nodes of the tree, find out whether there is a set of at mostktree edges whose removal separates all given pairs of nodes. MULTICUT has been intensively studied for trees as well as for general graphs mainly from the viewpoint of polynomial time approximation algorithms. By way of contrast, we provide a simple fixed‐parameter algorithm for MULTICUT IN TREES showing fixed‐parameter tractability with respect to parameterk. Moreover, based on some polynomial time data reduction rules, which appear to be of particular interest from an applied point of view, we show a problem kernel for MULTICUT IN TREES by an intricate mathematical analysis. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(3), 124–135 2005Keywords
This publication has 20 references indexed in Scilit:
- Exact algorithms and applications for Tree-like Weighted Set CoverJournal of Discrete Algorithms, 2006
- Experiments on data reduction for optimal domination in networksAnnals of Operations Research, 2006
- Minimal multicut and maximal integer multiflow: A surveyEuropean Journal of Operational Research, 2005
- Polynomial-time data reduction for dominating setJournal of the ACM, 2004
- Call control with k rejectionsJournal of Computer and System Sciences, 2003
- Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-widthJournal of Algorithms, 2003
- On efficient fixed-parameter algorithms for weighted vertex coverJournal of Algorithms, 2003
- Vertex Cover: Further Observations and Further ImprovementsJournal of Algorithms, 2001
- A general method to speed up fixed-parameter-tractable algorithmsInformation Processing Letters, 2000
- Advice classes of parameterized tractabilityAnnals of Pure and Applied Logic, 1997