Removing bottlenecks in the recognition of small $(k,\ell)$-graph classes
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910272213483520 |
|---|---|
| author | Bonomo-Braberman, Flavia Lin, Min Chih Maqueda, Ignacio |
| author_facet | Bonomo-Braberman, Flavia Lin, Min Chih Maqueda, Ignacio |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_17665 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Removing bottlenecks in the recognition of small $(k,\ell)$-graph classes Bonomo-Braberman, Flavia Lin, Min Chih Maqueda, Ignacio Discrete Mathematics 05C85 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. |
| title | Removing bottlenecks in the recognition of small $(k,\ell)$-graph classes |
| topic | Discrete Mathematics 05C85 |
| url | https://arxiv.org/abs/2510.17665 |