Room 327

Two set Cut-Uncut on Planar Graphs

Sounak Modak

In the Two-Sets Cut-Uncut problem on planar graphs, one is given an undirected planar graph $G$ and two sets of vertices $S$ and $T$. The question is, what is the minimum number of edges to remove from $G$, such that we separate all of $S$ from all of $T$, while maintaining that every vertex in $S$, and respectively in $T$, stays in the same connected component. This problem can be solved in time $2^{|S|+|T|}.n^{O(1)}$ with a one-sided error randomized algorithm. This algorithm implies a polynomial-time algorithm for the network diversion problem on planar graphs. More generally, Two-Sets Cut-Uncut remains fixed-parameter tractable even when parameterized by the number $r$ of faces in the plane graph covering the terminals $S\cup T$. In this talk we will see an fpt algorithm for the Two-Sets Cut-Uncut problem parameterized by facecover. (This is part of his credit seminar.)