License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.20
URN: urn:nbn:de:0030-drops-82458
URL: http://drops.dagstuhl.de/opus/volltexte/2017/8245/
Go to the corresponding LIPIcs Volume Portal


Chen, Li-Hsuan ; Hsieh, Sun-Yuan ; Hung, Ling-Ju ; Rossmanith, Peter

An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem

pdf-format:
LIPIcs-ISAAC-2017-20.pdf (0.5 MB)


Abstract

Given a graph G=(V, E), an s-plex S\subseteq V is a vertex subset such that for v\in S the degree of v in G[S] is at least |S|-s. An s-plex bipartition \mathcal{P}=(V_1, V_2) is a bipartition of G=(V, E), V=V_1\uplus V_2, satisfying that both V_1 and V_2 are s-plexes. Given an instance G=(V, E) and a parameter k, the s-Plex Bipartition problem asks whether there exists an s-plex bipartition of G such that min{|V_1|, |V_2|\}\leq k. The s-Plex Bipartition problem is NP-complete. However, it is still open whether this problem is fixed-parameter tractable. In this paper, we give a fixed-parameter algorithm for 2-Plex Bipartition running in time O*(2.4143^k). A graph G = (V, E) is called defective (p, d)-colorable if it admits a vertex coloring with p colors such that each color class in G induces a subgraph of maximum degree at most d. A graph G admits an s-plex bipartition if and only if the complement graph of G, \bar{G}, admits a defective (2, s-1)-coloring such that one of the two color classes is of size at most k. By applying our fixed-parameter algorithm as a subroutine, one can find a defective (2,1)-coloring with one of the two colors of minimum cardinality for a given graph in O*(1.5539^n) time where n is the number of vertices in the input graph.

BibTeX - Entry

@InProceedings{chen_et_al:LIPIcs:2017:8245,
  author =	{Li-Hsuan Chen and Sun-Yuan Hsieh and Ling-Ju Hung and Peter Rossmanith},
  title =	{{An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{20:1--20:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Yoshio Okamoto and Takeshi Tokuyama},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8245},
  URN =		{urn:nbn:de:0030-drops-82458},
  doi =		{10.4230/LIPIcs.ISAAC.2017.20},
  annote =	{Keywords: 2-plex, 2-plex bipartition, bounded-degree-1 set bipartition, defective (2,1)-coloring}
}

Keywords: 2-plex, 2-plex bipartition, bounded-degree-1 set bipartition, defective (2,1)-coloring
Seminar: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date: 2017
Date of publication: 04.12.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI