An efficient fixed-parameter algorithm for the 2-plex bipartition problem

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Given a graph G = (V,E), an s-plex S ⊆V is a vertex subset such that for v ? S the degree of v in G[S] is at least |S| s. An s-plex bipartition P = (V1, V2) is a bipartition of G = (V,E), V = V1 ] V2, satisfying that both V1 and V2 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{|V1|, |V2|} ≤ 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 fixedparameter algorithm for 2-Plex Bipartition running in time O∗(2.4143k). 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, 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.5539n) time where n is the number of vertices in the input graph.

Original languageEnglish
Title of host publication28th International Symposium on Algorithms and Computation, ISAAC 2017
EditorsTakeshi Tokuyama, Yoshio Okamoto
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770545
DOIs
Publication statusPublished - 2017 Dec 1
Event28th International Symposium on Algorithms and Computation, ISAAC 2017 - Phuket, Thailand
Duration: 2017 Dec 92017 Dec 22

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume92
ISSN (Print)1868-8969

Other

Other28th International Symposium on Algorithms and Computation, ISAAC 2017
CountryThailand
CityPhuket
Period17-12-0917-12-22

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'An efficient fixed-parameter algorithm for the 2-plex bipartition problem'. Together they form a unique fingerprint.

Cite this