License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2022.11
URN: urn:nbn:de:0030-drops-173679
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17367/
Go to the corresponding LIPIcs Volume Portal

Eiben, Eduard ; Rambaud, Clément ; Wahlström, Magnus

On the Parameterized Complexity of Symmetric Directed Multicut

pdf-format:
LIPIcs-IPEC-2022-11.pdf (0.8 MB)

Abstract

We study the problem Symmetric Directed Multicut from a parameterized complexity perspective. In this problem, the input is a digraph D, a set of cut requests C = {(s₁,t₁),…,(s_l,t_l)} and an integer k, and the task is to find a set X ⊆ V(D) of size at most k such that for every 1 ≤ i ≤ l, X intersects either all (s_i,t_i)-paths or all (t_i,s_i)-paths. Equivalently, every strongly connected component of D-X contains at most one vertex out of s_i and t_i for every i. This problem is previously known from research in approximation algorithms, where it is known to have an O(log k log log k)-approximation. We note that the problem, parameterized by k, directly generalizes multiple interesting FPT problems such as (Undirected) Vertex Multicut and Directed Subset Feedback Vertex Set. We are not able to settle the existence of an FPT algorithm parameterized purely by k, but we give three partial results: An FPT algorithm parameterized by k+l; an FPT-time 2-approximation parameterized by k; and an FPT algorithm parameterized by k for the special case that the cut requests form a clique, Symmetric Directed Multiway Cut. The existence of an FPT algorithm parameterized purely by k remains an intriguing open possibility.

BibTeX - Entry

@InProceedings{eiben_et_al:LIPIcs.IPEC.2022.11,
  author =	{Eiben, Eduard and Rambaud, Cl\'{e}ment and Wahlstr\"{o}m, Magnus},
  title =	{{On the Parameterized Complexity of Symmetric Directed Multicut}},
  booktitle =	{17th International Symposium on Parameterized and Exact Computation (IPEC 2022)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-260-0},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{249},
  editor =	{Dell, Holger and Nederlof, Jesper},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17367},
  URN =		{urn:nbn:de:0030-drops-173679},
  doi =		{10.4230/LIPIcs.IPEC.2022.11},
  annote =	{Keywords: Parameterized complexity, directed graphs, graph separation problems}
}

Keywords: Parameterized complexity, directed graphs, graph separation problems
Collection: 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Issue Date: 2022
Date of publication: 14.12.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI