Title: An FPT algorithm for planar multicuts with sources and sinks on the outer face,
Abstract: Given a list of k source-sink pairs in an edge-weighted graph G, the minimum
multicut problem consists in selecting a set of edges of minimum total weight
in G, such that removing these edges leaves no path from each source to its
corresponding sink. To the best of our knowledge, no non-trivial FPT result for
special cases of this problem, which is APX-hard in general graphs for any
fixed k>2, is known with respect to k only. When the graph G is planar, this
problem is known to be polynomial-time solvable if k=O(1), but cannot be FPT
with respect to k under the Exponential Time Hypothesis.
In this paper, we show that, if G is planar and in addition all sources and
sinks lie on the outer face, then this problem does admit an FPT algorithm when
parameterized by k (although it remains APX-hard when k is part of the input,
even in stars). To do this, we provide a new characterization of optimal
solutions in this case, and then use it to design a "divide-and-conquer"
approach: namely, some edges that are part of any such solution actually define
an optimal solution for a polynomial-time solvable multiterminal variant of the
problem on some of the sources and sinks (which can be identified thanks to a
reduced enumeration phase). Removing these edges from the graph cuts it into
several smaller instances, which can then be solved recursively.