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.ISAAC.2017.20
URN: urn:nbn:de:0030-drops-82458
URL: https://drops.dagstuhl.de/opus/volltexte/2017/8245/
 Go to the corresponding LIPIcs Volume Portal

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

 pdf-format:

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 Collection: 28th International Symposium on Algorithms and Computation (ISAAC 2017) Issue Date: 2017 Date of publication: 07.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy