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.ICALP.2018.112
URN: urn:nbn:de:0030-drops-91164
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9116/
Go to the corresponding LIPIcs Volume Portal

Xiao, Mingyu ; Nagamochi, Hiroshi

Brief Announcement: Bounded-Degree Cut is Fixed-Parameter Tractable

pdf-format:
LIPIcs-ICALP-2018-112.pdf (0.4 MB)

Abstract

In the bounded-degree cut problem, we are given a multigraph G=(V,E), two disjoint vertex subsets A,B subseteq V, two functions u_A, u_B:V -> {0,1,...,|E|} on V, and an integer k >= 0. The task is to determine whether there is a minimal (A,B)-cut (V_A,V_B) of size at most k such that the degree of each vertex v in V_A in the induced subgraph G[V_A] is at most u_A(v) and the degree of each vertex v in V_B in the induced subgraph G[V_B] is at most u_B(v). In this paper, we show that the bounded-degree cut problem is fixed-parameter tractable by giving a 2^{18k}|G|^{O(1)}-time algorithm. This is the first single exponential FPT algorithm for this problem. The core of the algorithm lies two new lemmas based on important cuts, which give some upper bounds on the number of candidates for vertex subsets in one part of a minimal cut satisfying some properties. These lemmas can be used to design fixed-parameter tractable algorithms for more related problems.

BibTeX - Entry

@InProceedings{xiao_et_al:LIPIcs:2018:9116,
  author =	{Mingyu Xiao and Hiroshi Nagamochi},
  title =	{{Brief Announcement: Bounded-Degree Cut is Fixed-Parameter Tractable}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{112:1--112:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9116},
  URN =		{urn:nbn:de:0030-drops-91164},
  doi =		{10.4230/LIPIcs.ICALP.2018.112},
  annote =	{Keywords: FPT, Important Cuts, Graph Cuts, Graph Algorithms}
}

Keywords: FPT, Important Cuts, Graph Cuts, Graph Algorithms
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

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