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.60
URN: urn:nbn:de:0030-drops-127272
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12727/
Go to the corresponding LIPIcs Volume Portal

Kurita, Kazuhiro ; Kobayashi, Yasuaki

Efficient Enumerations for Minimal Multicuts and Multiway Cuts

pdf-format:
LIPIcs-MFCS-2020-60.pdf (1 MB)

Abstract

Let G = (V, E) be an undirected graph and let B ⊆ V × V be a set of terminal pairs. A node/edge multicut is a subset of vertices/edges of G whose removal destroys all the paths between every terminal pair in B. The problem of computing a minimum node/edge multicut is NP-hard and extensively studied from several viewpoints. In this paper, we study the problem of enumerating all minimal node multicuts. We give an incremental polynomial delay enumeration algorithm for minimal node multicuts, which extends an enumeration algorithm due to Khachiyan et al. (Algorithmica, 2008) for minimal edge multicuts.
Important special cases of node/edge multicuts are node/edge multiway cuts, where the set of terminal pairs contains every pair of vertices in some subset T ⊆ V, that is, B = T × T. We improve the running time bound for this special case: We devise a polynomial delay and exponential space enumeration algorithm for minimal node multiway cuts and a polynomial delay and space enumeration algorithm for minimal edge multiway cuts.

BibTeX - Entry

@InProceedings{kurita_et_al:LIPIcs:2020:12727,
  author =	{Kazuhiro Kurita and Yasuaki Kobayashi},
  title =	{{Efficient Enumerations for Minimal Multicuts and Multiway Cuts}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{60:1--60: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/12727},
  URN =		{urn:nbn:de:0030-drops-127272},
  doi =		{10.4230/LIPIcs.MFCS.2020.60},
  annote =	{Keywords: Multicuts, Multiway cuts, Enumeration algorithms}
}

Keywords: Multicuts, Multiway cuts, Enumeration algorithms
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020

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