2026-08-16T22:51:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8245 2024-03-06T10:41:48Z ddc:004 open_access

An Efficient Fixed-Parameter Algorithm for the 2-Plex Bipartition Problem Chen, Li-Hsuan Hsieh, Sun-Yuan Hung, Ling-Ju Rossmanith, Peter 2-plex 2-plex bipartition bounded-degree-1 set bipartition defective (2,1)-coloring 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Li-Hsuan Chen and Sun-Yuan Hsieh and Ling-Ju Hung and Peter Rossmanith 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.20 urn:nbn:de:0030-drops-82458 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.20 eng https://creativecommons.org/licenses/by/3.0/legalcode