Computer Science – Data Structures and Algorithms
Scientific paper
2011-11-09
Computer Science
Data Structures and Algorithms
Scientific paper
Recent work of the present authors provided a polynomial kernel for Odd Cycle Transversal by introducing matroid-based tools into kernelization. In the current work we further establish the usefulness of matroid theory to kernelization by showing applications of a result on representative sets due to Lov\'asz (Combinatorial Surveys 1977) and Marx (TCS 2009). We give two types of applications: 1. Direct applications of the representative objects idea. In this direction, we give a polynomial kernel for Almost 2-SAT by reducing the problem to a cut problem with pairs of vertices as sinks, and subsequently reducing the set of pairs to a representative subset of bounded size. This implies polynomial kernels for several other problems, including Vertex Cover parameterized by the size of the LP gap, and the RHorn-Backdoor Deletion Set problem from practical SAT solving. We also get a polynomial kernel for Multiway Cut with deletable terminals, by producing a representative set of vertices, of bounded size, which is guaranteed to contain an optimal solution. 2. A dual application to irrelevant vertex arguments. By using representative sets to extract a set containing all vertices which are members of every optimal solution, we may label the remaining vertices as irrelevant and make any one of them undeletable. Iterating the rule gives a polynomial kernel. This gives a polynomial kernel for Multiway Cut with s terminals, Multicut with s terminal pairs, and for Group Feedback Arc/Vertex Set problems over groups with s elements, for s constant. Generally, our new irrelevant vertex approach allows reduction rule-based kernelizations for all mentioned problems, improving over the essentially black box approach for Odd Cycle Transversal. A small amount of randomization is required in order to find representations of certain gammoids necessary to invoke the Lov\'asz/Marx result.
Kratsch Stefan
Wahlström Magnus
No associations
LandOfFree
Representative sets and irrelevant vertices: New tools for kernelization 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 Representative sets and irrelevant vertices: New tools for kernelization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Representative sets and irrelevant vertices: New tools for kernelization will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-42653