License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.70
URN: urn:nbn:de:0030-drops-127391
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12739/
Misra, Pranabendu ;
Panolan, Fahad ;
Rai, Ashutosh ;
Saurabh, Saket ;
Sharma, Roohani
Quick Separation in Chordal and Split Graphs
Abstract
In this paper we study two classical cut problems, namely Multicut and Multiway Cut on chordal graphs and split graphs. In the Multicut problem, the input is a graph G, a collection of ? vertex pairs (s_i, t_i), i ∈ [?], and a positive integer k and the goal is to decide if there exists a vertex subset S ⊆ V(G)⧵ {s_i,t_i : i ∈ [?]} of size at most k such that for every vertex pair (s_i,t_i), s_i and t_i are in two different connected components of G-S. In Unrestricted Multicut, the solution S can possibly pick the vertices in the vertex pairs {(s_i,t_i): i ∈ [?]}. An important special case of the Multicut problem is the Multiway Cut problem, where instead of vertex pairs, we are given a set T of terminal vertices, and the goal is to separate every pair of distinct vertices in T× T. The fixed parameter tractability (FPT) of these problems was a long-standing open problem and has been resolved fairly recently. Multicut and Multiway Cut now admit algorithms with running times 2^{{?}(k³)}n^{{?}(1)} and 2^k n^{{?}(1)}, respectively. However, the kernelization complexity of both these problems is not fully resolved: while Multicut cannot admit a polynomial kernel under reasonable complexity assumptions, it is a well known open problem to construct a polynomial kernel for Multiway Cut. Towards designing faster FPT algorithms and polynomial kernels for the above mentioned problems, we study them on chordal and split graphs. In particular we obtain the following results.
1) Multicut on chordal graphs admits a polynomial kernel with {?}(k³ ?⁷) vertices. Multiway Cut on chordal graphs admits a polynomial kernel with {?}(k^{13}) vertices.
2) Multicut on chordal graphs can be solved in time min {?(2^{k} ⋅ (k³+?) ⋅ (n+m)), 2^{?(? log k)} ⋅ (n+m) + ? (n+m)}. Hence Multicut on chordal graphs parameterized by the number of terminals is in XP.
3) Multicut on split graphs can be solved in time min {?(1.2738^k + kn+?(n+m), ?(2^{?} ⋅ ? ⋅ (n+m))}. Unrestricted Multicut on split graphs can be solved in time ?(4^{?}⋅ ? ⋅ (n+m)).
BibTeX - Entry
@InProceedings{misra_et_al:LIPIcs:2020:12739,
author = {Pranabendu Misra and Fahad Panolan and Ashutosh Rai and Saket Saurabh and Roohani Sharma},
title = {{Quick Separation in Chordal and Split Graphs}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {70:1--70:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-159-7},
ISSN = {1868-8969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12739},
URN = {urn:nbn:de:0030-drops-127391},
doi = {10.4230/LIPIcs.MFCS.2020.70},
annote = {Keywords: chordal graphs, multicut, multiway cut, FPT, kernel}
}
|
Keywords: |
|
chordal graphs, multicut, multiway cut, FPT, kernel |
|
Collection: |
|
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
18.08.2020 |
