Removing bottlenecks in the recognition of small $(k,\ell)$-graph classes
This work provides more efficient recognition algorithms for specific graph classes, which is relevant for researchers and practitioners working with graph theory and algorithm design, particularly in areas where these graph structures are encountered. It is an incremental improvement to existing algorithms.
This paper addresses the recognition problem for small $(k,\\ell)$-graph classes, which are graphs whose vertex sets can be partitioned into $k$ independent sets and $\\ell$ cliques. The authors present improved algorithms for $(2,1)$-, $(1,2)$-, and $(2,2)$-graphs, reducing the running time for $(2,1)$-graphs from $O((n+m)^2)$ to $O(n(n+m))$ and for $(2,2)$-graphs to $O(n^4(n+\\min\\{m,\\overline m\\})^3)$.
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\geq 3$ or $\ell\geq 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.