Skip to Main content Skip to Navigation
Journal articles

An FPT Algorithm for Planar Multicuts with Sources and Sinks on the Outer Face

Cédric Bentz 1
1 CEDRIC - OC - CEDRIC. Optimisation Combinatoire
CEDRIC - Centre d'études et de recherche en informatique et communications
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 ≥ 3, 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-cnam.archives-ouvertes.fr/hal-02444156
Contributor : Cédric Bentz <>
Submitted on : Monday, January 20, 2020 - 4:00:24 PM
Last modification on : Friday, August 21, 2020 - 1:56:05 PM
Long-term archiving on: : Tuesday, April 21, 2020 - 5:19:01 PM

File

1708.05903.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Cédric Bentz. An FPT Algorithm for Planar Multicuts with Sources and Sinks on the Outer Face. Algorithmica, Springer Verlag, 2019, 81 (1), pp.224-237. ⟨10.1007/s00453-018-0443-4⟩. ⟨hal-02444156⟩

Share

Metrics

Record views

100

Files downloads

98