TY - GEN

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

AU - Chen, Li Hsuan

AU - Hsieh, Sun Yuan

AU - Hung, Ling Ju

AU - Rossmanith, Peter

PY - 2017/12/1

Y1 - 2017/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85038556053&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85038556053&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ISAAC.2017.20

DO - 10.4230/LIPIcs.ISAAC.2017.20

M3 - Conference contribution

AN - SCOPUS:85038556053

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 28th International Symposium on Algorithms and Computation, ISAAC 2017

A2 - Tokuyama, Takeshi

A2 - Okamoto, Yoshio

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 28th International Symposium on Algorithms and Computation, ISAAC 2017

Y2 - 9 December 2017 through 22 December 2017

ER -