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
N1 - Funding Information:
∗ Parts of this work were supported by the Ministry of Science and Technology of Taiwan under grants MOST 105–2221–E–006–164–MY3 and MOST 103–2221–E–006–135–MY3. † Li-Hsuan Chen is supported by the Ministry of Science and Technology of Taiwan under grant MOST 106– 2811–E–006–008 ‡ Ling-Ju Hung is supported by the Ministry of Science and Technology of Taiwan under grant MOST 106– 2811–E–006–055.
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 -