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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8245/
Chen, Li-Hsuan ;
Hsieh, Sun-Yuan ;
Hung, Ling-Ju ;
Rossmanith, Peter
An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem
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 |
