Removing bottlenecks in the recognition of small $(k,\ell )$-graph classes

Abstract

A graph is a $(k,\ell )$-graph if its vertex set can be partitioned into $k$ independent sets and $\ell$ cliques. This family simultaneously generalizes split, bipartite, and co-bipartite graphs. While the recognition problem is NP-complete whenever $k\ge 3$ or $\ell \ge 3$, the remaining small cases are polynomial-time solvable. In this paper we revisit the known recognition algorithms for the first nontrivial polynomial cases, namely $(2,1)$-, $(1,2)$-, and $(2,2)$-graphs, and show how to remove specific bottlenecks in their existing recognition procedures. For $(2,1)$-graphs, we show that the extra quadratic enumeration in the algorithm of Brandstädt, Le and Szymczak can be avoided by exploiting the structure of a shortest odd cycle in the relevant residual graph, reducing the running time from $O((n+m{)}^2)$ to $O(n(n+m))$. By complementation, this yields an $O(n(n+\overline{m}))$-time recognition algorithm for $(1,2)$-graphs, where $\overline{m}$ denotes the number of edges of the complement graph. For $(2,2)$-graphs, we refine the sparse-dense partition framework of Feder, Hell, Klein and Motwani by restricting the local-search enumeration to sets that are simultaneously bipartite and co-bipartite, and by using the improved algorithms for $(2,1)$- and $(1,2)$-graphs as preprocessing tools. This gives an $O(n^4(n+\min \{m,\overline{m}\}{)}^3)$-time recognition algorithm for $(2,2)$-graphs.

23 pages, 0 figures