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

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 = (V₁, V₂) is a bipartition of G = (V,E), V = V₁ ] V₂, satisfying that both V₁ and V₂ 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₁|, |V₂|} ≤ 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.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, 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ⁿ) time where n is the number of vertices in the input graph.