Efficient recognition algorithms for \((1,2)\)-, \((2,1)\)- and \((2,2)\)-graphs
October 20, 2025
Abstract
A graph \(G\) is said to be a \((k,\ell)\)-graph if its vertex set can be partitioned into \(k\) independent sets and \(\ell\) cliques. It is well established that the recognition problem for \((k,\ell)\)-graphs is NP-complete whenever \(k \geq 3\) or \(\ell \geq 3\), while it is solvable in polynomial time otherwise. In particular, for the case \(k+\ell \leq 2\), recognition can be carried out in linear time, since split graphs coincide with the class of \((1,1)\)-graphs, bipartite graphs correspond precisely to \((2,0)\)-graphs, and \((\ell,k)\)-graphs are the complements of \((k,\ell)\)-graphs. Recognition algorithms for \((2,1)\)- and \((1,2)\)-graphs were provided in [Brandstädt, Le and Szymczak, Discrete Applied Mathematics 89 (1998), pp. 59–73], while the case of \((2,2)\)-graphs was addressed in [Feder, Hell, Klein, and Motwani, Proceedings of STOC’99, pp. 464–472]. In this work, we refine these results by presenting improved recognition algorithms with lower time complexity. Specifically, we reduce the running time from \(O((n+m)^2)\) to \(O(n^2+nm)\) for \((2,1)\)-graphs, from \(O((n+\overline{m})^2)\) to \(O(n^2+n\overline{m})\) for \((1,2)\)-graphs, and from \(O(n^{10}(n+m))\) to \(O(n^4 (n+\min\{m,\overline{m}\})^3)\) for \((2,2)\)-graphs. Here, \(n\) and \(m\) denote the number of vertices and edges of the input graph \(G\), respectively, and \(\overline{m}\) denotes the number of edges in the complement of \(G\).
Partitions of graphs into independent sets and cliques ,Generalization of bipartite and split graphs ,Polynomial time recognition
1 Introduction↩︎
A graph \(G=(V,E)\) is called a \((k,\ell)\)-graph if its vertex set \(V\) can be partitioned into \(k\) independent sets and \(\ell\) cliques. This notion was first introduced by Brandstädt [1] in 1996. Later, in 2003, Alekseev and Lozin [2] independently defined a graph to be \((p,q)\)-colorable if its vertices can be partitioned into at most \(p\) cliques and \(q\) independent sets. They further showed that the problem of finding a maximum-weight independent set is polynomial time solvable within this class of graphs if and only if \(q \leq 2\) (assuming \(P \neq NP\)).
The family of \((k,\ell)\)-graphs naturally generalizes several well-known classes: split graphs (\((1,1)\)-graphs), bipartite graphs (\((2,0)\)-graphs), and co-bipartite graphs (\((0,2)\)-graphs). For each of these three classes, linear time recognition algorithms are available. On the other hand, the recognition problem is NP-complete for all cases with \(k \geq 3\) or \(l \geq 3\) [1], [3].
In [1], Brandstädt proposed \(O(|V|^3)\) time algorithms for recognizing \((2,1)\)- and \((1,2)\)-graphs, along with an \(O(|V|^4)\) time algorithm for \((2,2)\)-graphs. However, two years later, a corrigendum [3] reported that these algorithms were incorrect. In the same year, an \(O((|V|+|E|)^2)\) time recognition algorithm for \((2,1)\)-graphs was presented in [4]. Subsequently, Feder et al. [5] developed polynomial time algorithms for recognizing \((2,1)\)- and \((2,2)\)-graphs as part of a broader study on “sparse-dense” partition problems, which were clearly motivated by \((k,l)\)-graph recognition. The recognition algorithm for \((2,2)\)-graphs derived from their framework has time complexity \(O(|V|^{10}(|V|+|E|))\).
Table 1 summarizes the most efficient recognition algorithms currently known (to the best of our knowledge), together with their sources, and highlights our improvements for \((2,1)\)-, \((1,2)\)-, and \((2,2)\)-graphs. Here, \(n = |V|\), \(m = |E|\), and \(\overline{m} = \binom{n}{2} - m\).
| Graph Class | Current Best Algorithm | Ref. | Improvement |
|---|---|---|---|
| \((2,1)\)-graphs | \(O((n+m)^2)\) | [4] | \(O(n(n+m))\) |
| \((1,2)\)-graphs | \(O((n+\overline{m})^2)\) | [4] | \(O(n(n+\overline{m}))\) |
| \((2,2)\)-graphs | \(O(n^{10}(n+m))\) | [5] | \(O(n^4 (n+\min\{m,\overline{m}\})^3)\) |
Further studies on \((k,\ell)\)-graphs have been carried out within specific graph classes, such as chordal graphs [6], cographs [7], and line graphs [8]. In addition, research has also addressed the recognition of \((k,\ell)\)-probe graphs, both in the case of fixed partitions [9] and in the unpartitioned setting [10].
2 Preliminaries↩︎
In this section, we briefly describe the currently best-known algorithms to recognize \((2,1)\)-, \((1,2)\)-, and \((2,2)\)-graphs, respectively.
First, we introduce some auxiliary definitions and notations to facilitate the understanding of these algorithms and the remainder of this work.
Given a graph \(G = (V, E)\), let \(n = |V|\) and \(m = |E|\).
\(V(G)\) and \(E(G)\) denote the vertex set and edge set of \(G\), respectively, if they are not explicitly specified.
For any subset \(W \subseteq V\), \(G[W]\) denotes the subgraph of \(G\) induced by \(W\).
For any vertex \(v \in V\):
the open neighborhood of \(v\) in \(G\) is \(N_G(v) = \{ w \in V : (v, w) \in E \}\),
the closed neighborhood of \(v\) in \(G\) is \(N_G[v] = N_G(v) \cup \{v\}\),
the non-neighborhood of \(v\) in \(G\) is \(\overline{N_G}(v) = V \setminus N_G[v] = N_{\overline{G}}(v)\), where \(\overline{G}\) denotes the complement of \(G\).
When the context is clear, subscripts may be omitted.
\(\omega(G)\) denotes the size of a maximum clique in \(G\).
In [4], an algorithm (Algorithm 1) is presented to recognize whether a graph is a \((2,1)\)-graph in time \(O((n+m)^2)\). Below, we show the main part of this algorithm (excluding the Modify procedure) with minor syntactical adaptations. Since a graph \(G\) is a \((k, \ell)\)-graph if and only if its complement \(\overline{G}\) is a \((\ell, k)\)-graph, \((1,2)\)-graphs can be recognized in \(O((n+\overline{m})^2)\) time, where \(\overline{m}\) is the number of edges in \(\overline{G}\). The authors of [4] use \(\boldsymbol{(k,\ell)}\) to denote the class of \((k,\ell)\)-graphs. They also pointed out that their algorithm runs in \(O(n(n+m))\) time except for Steps (27)–(32) (the case when \(\omega(G[R]) \leq 2\)).
![Figure 1: [4]](/article/2510.17665/_pdflatex/kjauylig.png "fig:")
![Figure 2: [5]](/article/2510.17665/_pdflatex/nuemyiax.png "fig:")
In [5], the authors introduced the following framework. Let \(\mathcal{S}\) and \(\mathcal{D}\) be two graph classes, called sparse and dense, respectively, such that for some constant \(c\) every \(S\in\mathcal{S}\) and \(D\in\mathcal{D}\) intersect in at most \(c\) vertices. A sparse–dense partition of a graph \(G=(V,E)\) (with respect to \(\mathcal{S}\) and \(\mathcal{D}\)) is a partition \(V=V_S\cup V_D\) with \(V_S\cap V_D=\emptyset\), where \(G[V_S]\in\mathcal{S}\) and \(G[V_D]\in\mathcal{D}\). They proved the following theorem and, in the course of its proof, implicitly described an algorithm that finds all sparse–dense partitions in time \(O(n^{2c+2}T(n))\), where \(T(n)\) is the running time of the recognition procedures for \(\mathcal{S}\) and \(\mathcal{D}\) (on \(n\)-vertex graphs). Algorithm 2 above makes this algorithm explicit.
Theorem 1 ([5]). A graph on \(n\) vertices has at most \(n^{2c}\) different sparse–dense partitions. Furthermore, all these partitions can be found in time \(n^{2c+2}\,T(n)\), where \(T(n)\) is the time required to recognize membership in \(\mathcal{S}\) and in \(\mathcal{D}\).
Running time of Algorithm 2. Phase I examines \(O(n^{2c+1})\) candidates per iteration and performs at most \(O(n)\) improvements; Phase II checks \(O(n^{2c})\) candidates. As the membership in \(\mathcal{S}\) and \(\mathcal{D}\) can be recognized in time \(T(n)\), the overall running time is \(O\!\left(n^{2c+2}T(n)\right)\).
It is immediate that recognizing whether a graph \(G=(V,E)\) is a \((2,2)\)-graph is equivalent to deciding whether there exists a partition \((W,V\setminus W)\) of \(V\) such that \(G[W]\) is bipartite and \(G[V\setminus W]\) is co-bipartite. This fits the sparse–dense framework by taking sparse \(=\,\)bipartite and dense \(=\,\)co-bipartite, for which one can take \(c=4\). In this setting, Algorithm 2 recognizes \((2,2)\)-graphs in time \(O\!\left(n^{10}(n+m)\right)\), since both bipartite and co-bipartite recognitions can be done in linear time (thus \(T(n)=\Theta(n+m)\)).
3 \((2,1)\)- and \((1,2)\)-graphs↩︎
In this section, we propose an improvement to Algorithm 1 that reduces the time complexity to \(O(n(n+m))\).
Theorem 2. It can be decided in \(O(n(n+m))\) time whether a graph \(G = (V, E)\) belongs to the class \(\boldsymbol{(2,1)}\).
Proof. It suffices to modify Steps (27)–(32) of Algorithm 1 so that these steps also run in \(O(n(n+m))\) time.
After completing Steps (1)–(26), the vertex set of \(G\) is partitioned into the following subsets:
\(C^F\): a clique consisting of all vertices \(v\) such that \(G[N(v)] \notin \boldsymbol{(1,1)}\) and \(G[\overline{N}(v)] \in \boldsymbol{(2,0)}\);
\(B^F\): a set inducing a bipartite subgraph, consisting of all vertices \(v\) such that \(G[N(v)] \in \boldsymbol{(1,1)}\) and \(G[\overline{N}(v)] \notin \boldsymbol{(2,0)}\);
\(R\): the set of vertices such that \(G[N(v)] \in \boldsymbol{(1,1)}\) and \(G[\overline{N}(v)] \in \boldsymbol{(2,0)}\).
Furthermore, we know that \(R\) is nonempty and that \(\omega(G[R]) \leq 2\).
Our goal is to determine whether there exists a partition of the vertices of \(G\) into two sets \(C\) and \(B\) such that \(C\) induces a clique and \(G[B]\) is bipartite. To this end, we attempt to partition the vertices of \(R\) into these two sets while keeping \(B^F \subseteq B\) and \(C^F \subseteq C\).
If \(B = B^F \cup R\) induces a bipartite subgraph \(G[B]\), we define \(C = C^F\). Since \(C\) is a clique, we conclude that \(G \in \boldsymbol{(2,1)}\).
Otherwise, let \(C_{2k+1}\) be the smallest odd cycle in \(G[B^F \cup R]\). Such a cycle can be found in \(O(n(n+m))\) time using breadth-first search (BFS) from each vertex of \(R\), because this cycle must contain at least one vertex from \(R\). Since we require \(G[B]\) to be bipartite, it cannot occur that \(V(C_{2k+1}) \subseteq B\). Therefore, it suffices to verify whether any of the following definitions of \(C\) and \(B\) yield a valid partition such that \(C\) is a clique and \(G[B]\) is bipartite:
For each vertex \(v \in V(C_{2k+1}) \cap R\), define \[C = C^F \cup \{v\}, \quad B = B^F \cup (R \setminus \{v\}).\]
For each edge \(e = (v, w)\) having at least one endpoint in \(V(C_{2k+1})\) and both endpoints in \(R\), define \[C = C^F \cup \{v, w\}, \quad B = B^F \cup (R \setminus \{v, w\}).\]
If none of these cases yield a pair \((C,B)\) satisfying the required properties, then \(G \notin \boldsymbol{(2,1)}\).
Each such verification takes \(O(n+m)\) time. To achieve the proposed total complexity, we must ensure that at most \(O(n)\) such checks are performed. In case (a), there are clearly \(O(n)\) checks. It remains to show that the number of edges considered in case (b) is also at most \(O(n)\).
◻
To complete the previous proof, it suffices to establish the following proposition.
Proposition 1. Let \(H\) be a non-bipartite graph, and let \(C_{2k+1}\) be its shortest odd cycle. Then there exist at most \(O(n)\) edges in \(H\) with at least one endpoint in \(V(C_{2k+1})\).
Proof. If \(k = 1\), i.e., \(C_{2k+1} = K_3\), then each vertex in \(K_3\) has at most \(O(n)\) neighbors in \(V(H) \setminus V(C_{2k+1})\). Since \(K_3\) contains three edges, the total number of edges incident to \(V(C_{2k+1})\) is \(O(3n + 3) = O(n)\).
If \(k > 1\), we first show that for each vertex \(v \in V(H) \setminus V(C_{2k+1})\), there are at most two edges between \(v\) and \(V(C_{2k+1})\). Let \(V(C_{2k+1}) = v_1 v_2 \dots v_{2k+1} v_1\). Assume, without loss of generality, that \(v\) is adjacent to \(v_1\).
\(v\) cannot be adjacent to \(v_2\), since this would create the triangle \(v v_1 v_2 v\). Similarly, \(v\) cannot be adjacent to \(v_{2k+1}\).
For all \(4 \leq j \leq 2k-1\), \(v\) cannot be adjacent to \(v_j\), because that would create an odd cycle of length strictly less than \(2k+1\): if \(j\) is even, the cycle \(v v_1 \dots v_j v\); if \(j\) is odd, the cycle \(v v_j \dots v_{2k+1} v_1 v\).
Furthermore, \(v\) cannot be simultaneously adjacent to both \(v_3\) and \(v_{2k}\), as this would form an odd cycle \(v v_3 \dots v_{2k} v\) of length \(2k-1\), again shorter than \(2k+1\). Therefore, \(v\) has at most two neighbors in the cycle (either \(\{v_1, v_3\}\) or \(\{v_1, v_{2k}\}\)).
In total, the cycle itself contributes \(O(n)\) edges, and each vertex outside the cycle contributes at most two edges connecting it to the cycle. Thus, the total number of edges with at least one endpoint in \(V(C_{2k+1})\) is \(O(n + 2n) = O(n)\). ◻
In [11], a linear time algorithm is proposed to find the intersection of all odd cycles in a graph. Using this algorithm, we propose an alternative way to perform the improvement discussed above, which leads to a different proof of Theorem 2.
Proof. This alternative method proceeds as follows:
As before, if \(B = B^F \cup R\) induces a bipartite subgraph \(G[B]\), then \(C = C^F\) is a clique, and consequently \(G \in \boldsymbol{(2,1)}\).
Determine in \(O(n+m)\) time the subset \[R^\star = \{\, v \in R : C^F \subseteq N_G(v) \,\}\] of \(R\). If \(R^\star = \emptyset\), then \(G \notin \boldsymbol{(2,1)}\), since the desired clique \(C\) must be both a superset of \(C^F\) and a subset of \(C^F \cup R^\star\).
Apply the algorithm of [11] to the graph \(G[B^F \cup R]\) to compute the set \(I_v\) of all vertices belonging to every odd cycle of \(G[B^F \cup R]\). This step takes \(O(n+m)\) time.
- If \(I_v \cap R^\star \neq \emptyset\), choose any vertex \(w \in I_v \cap R^\star\). Define \[C = C^F \cup \{w\}, \quad B = B^F \cup (R \setminus \{w\}).\] Then \(C\) is a clique and \(G[B]\) is bipartite. Hence, \(G \in \boldsymbol{(2,1)}\).
For each vertex \(v \in R^\star\), run the algorithm of [11] on the graph \(G[B^F \cup (R \setminus \{v\})]\) to obtain the set \[I'_v = \text{the set of vertices belonging to all odd cycles of } G[B^F \cup (R \setminus \{v\})].\]
- If there exists a vertex \(w \in I'_v \cap N(v) \cap R^\star\), define \[C = C^F \cup \{v, w\}, \quad B = B^F \cup (R \setminus \{v, w\}).\] It follows that \(C\) is a clique and \(G[B]\) is bipartite, implying that \(G \in \boldsymbol{(2,1)}\).
If none of the above conditions are satisfied, then \(G \notin \boldsymbol{(2,1)}\).
The dominant cost arises from the \(O(n)\) applications of the algorithm from [11], resulting in an overall running time of \(O(n(n+m))\). ◻
4 \((2,2)\)-graphs↩︎
In Section 2, Algorithm 2 is presented; it can be used to recognize whether a graph is a \((2,2)\)-graph in time \(O(n^{10}(n+m))\), considering bipartite graphs as sparse, co-bipartite graphs as dense, and taking \(c = 4\).
We propose a series of improvements to this algorithm for \((\boldsymbol{2},\boldsymbol{2})\)-recognition that reduce its time complexity to \(O\!\left(n^4 (n + \min\{m,\overline{m}\})^3\right)\).
Phase modifications. We first introduce a minor modification to the implementation of both Phase I and Phase II that does not affect the overall asymptotic complexity. In each phase, when searching for a candidate neighbor, a subset of vertices \(P\) is first removed and another subset \(Q\) is subsequently added. We impose the condition that \(P\) and \(Q\) must be disjoint.
A direct observation from Algorithm 2.
Observation 1. After Phase I, it holds that \(|S^\star| \ge |V_S|\) for any sparse–dense partition \((V_S, V_H)\) of \(G\), provided such a partition exists.
If \(|S^\star| < |V_S|\), then the set \(P = S^\star \setminus V_S = S^\star \cap V_H\) can be removed, and a set of \(|P| + 1\) vertices from \(V_S \setminus S^\star\) can be added. Since \(|P| \le c\), because \(P\) lies in the intersection of a sparse and a dense induced subgraph, this operation would yield a new improvement—contradicting the fact that Phase I has already terminated.
In Phase II, to obtain \(V_S\) of a sparse–dense partition \((V_S, V_H)\) of \(G\), it is necessary to remove vertices of \(P = S^\star \setminus V_S = S^\star \cap V_H\) and add vertices of \(Q = V_S \setminus S^\star\). Once again, \(P\) represents the intersection between a sparse and a dense induced subgraph.
Characterization of \(G[P]\). In our setting, sparse corresponds to bipartite graphs, dense to co-bipartite graphs, and \(c = 4\). In both phases of the algorithm, it suffices to consider subsets \(P \subseteq S^\star\) with \(|P| \le 4\) such that \(G[P]\) is both bipartite and co-bipartite. Therefore, \(G[P]\) is isomorphic to one of the following graphs:
the empty graph,
the trivial graph \(K_1\),
\(K_2\),
\(2K_1 = \overline{K_2}\),
\(K_1 + K_2 = \overline{K_{1,2}}\),
\(K_3 - \{e\} = K_{1,2}\),
\(2K_2 = \overline{C_4}\),
\(P_4\),
\(C_4\).
The number of such induced subgraphs in \(G\) is \(O((n+m)^2)\), and all of them can be generated within this time bound. Consequently, the number of candidates per iteration in Phase I is reduced to \(O(n^5 (n+m)^2)\), while Phase II now examines \(O(n^4 (n+m)^2)\) candidates. Hence, the overall time complexity for \((\boldsymbol{2},\boldsymbol{2})\)-recognition becomes \(O(n^6 (n+m)^3)\).
Second improvement. A further optimization can be achieved as follows. Given a subset \(P\), define \(B' \coloneq S^\star \setminus P\). Since \(G[B']\) is bipartite, we compute its connected components by identifying the vertices in each bipartition of every component, which requires \(O(n+m)\) time.
Next, we must find a subset \(Q\) of \(|P| + 1\) vertices such that \(Q \cap P = \emptyset\) and \(G[B' \cup Q]\) remains bipartite. We proceed as follows. First, we attempt to add a vertex \(q_1 \in V \setminus (B' \cup P)\) and check whether \(G[B' \cup \{q_1\}]\) is bipartite. If it is not, we try another vertex from \(V \setminus (B' \cup P)\). If no such vertex exists, it means that for this particular \(P\), there is no way to increase the cardinality of \(S^\star\).
If \(G[B' \cup \{q_1\}]\) is bipartite, two cases arise:
If \(P = \emptyset\), we have already found a way to enlarge \(S^\star\).
Otherwise, we must continue by adding at least one more vertex \(q_2\).
To verify that \(G[B' \cup \{q_1\}]\) is bipartite, it suffices to traverse the neighbors of \(q_1\) and ensure that \(q_1\) has no neighbors in both partitions of the same connected component of \(G[B']\). This verification takes \(O(d(q_1))\) time.
If a second vertex \(q_2\) needs to be added, we compute the connected components of \(G[B' \cup \{q_1\}]\). Those components of \(G[B']\) that do not contain neighbors of \(q_1\) remain independent components of \(G[B' \cup \{q_1\}]\). The remaining components of \(G[B']\) are merged into a single connected component containing \(q_1\), as follows: let \(C\) be one of these components with bipartitions \((C^+, C^-)\) such that \(N(q_1) \cap C^+ \ne \emptyset\). Then \(C^+\) belongs to the partition opposite to \(q_1\), while \(C^-\) belongs to the same partition as \(q_1\). This computation costs \(O(n)\).
The same reasoning applies for \(q_2, \dots, q_{|Q|}\). For the final vertex \(q_{|Q|}\), it is no longer necessary to add additional vertices or recompute connected components for a larger induced subgraph. This reduces the total time complexity to \[O\!\big(n (n+m)^2 \, n^4 (n+m)\big) = O(n^5 (n+m)^3).\]
Third improvement. A third optimization can be introduced as follows. For each vertex \(v \in V\), we check:
whether \(G[N(v)] \in (\boldsymbol{1},\boldsymbol{2})\), and
whether \(G[V \setminus N[v]] \in (\boldsymbol{2},\boldsymbol{1})\).
These checks can clearly be performed for all vertices in total time \(O(n^2(n+m))\).
Let
\(B^F \coloneq \{\, v \in V : G[N(v)] \in (\boldsymbol{1},\boldsymbol{2}) \wedge G[V \setminus N[v]] \notin (\boldsymbol{2},\boldsymbol{1}) \,\}\),
\(C^F \coloneq \{\, v \in V : G[N(v)] \notin (\boldsymbol{1},\boldsymbol{2}) \wedge G[V \setminus N[v]] \in (\boldsymbol{2},\boldsymbol{1}) \,\}\),
\(R \coloneq \{\, v \in V : G[N(v)] \in (\boldsymbol{1},\boldsymbol{2}) \wedge G[V \setminus N[v]] \in (\boldsymbol{2},\boldsymbol{1}) \,\}\).
If \(V \ne B^F \cup C^F \cup R\) (i.e., there exists \(v \in V\) such that both tests fail), or if \(G[B^F]\) is not bipartite, or \(G[C^F]\) is not co-bipartite, then \(G \notin (\boldsymbol{2},\boldsymbol{2})\).
Assume that \(G \in (\boldsymbol{2},\boldsymbol{2})\) and let \((B^\star ,C^\star )\) be a sparse–dense partition of \(G\). Clearly, \(B^F \subseteq B^\star\) and \(C^F \subseteq C^\star\). If \(R = \emptyset\), then \(B^F = B^\star\) and \(C^F = C^\star\), and \(G\) is a \((2,2)\)-graph if and only if \(G[B^F]\) is bipartite and \(G[C^F]\) is co-bipartite.
If \(R \ne \emptyset\), we select a vertex \(v \in R\) of minimum degree and decompose \[N[v] = C_1 \cup C_2 \cup I_3, \quad V \setminus N[v] = C_3 \cup I_1 \cup I_2,\] where \(v \in C_1\), each \(C_i\) is a clique, and each \(I_k\) is an independent set (\(1 \le i,k \le 3\)). Clearly, \(I_k \setminus B^\star \subseteq C^\star\) and \(|I_k \setminus B^\star | \le 2\) for all \(1 \le k \le 3\).
We now seek a subset \(B \subseteq I_1 \cup I_2 \cup I_3\) of maximum cardinality such that:
\(G[B]\) is bipartite,
\(B^F \cap (I_1 \cup I_2 \cup I_3) \subseteq B\),
\(C^F \cap B = \emptyset\), and
\(G[(I_1 \cup I_2 \cup I_3) \setminus B]\) is co-bipartite, in particular \(|I_k \setminus B| \le 2\) for all \(1 \le k \le 3\).
Clearly, \(|B| \ge |(I_1 \cup I_2 \cup I_3) \cap B^\star |\) and \(|B^\star \setminus (I_1 \cup I_2 \cup I_3)| \le 6\), since \(|B^\star \cap C_k| \le 2\) for \(1 \le k \le 3\). Therefore, \(|B| + 6 \ge |B^\star |\). Once \(B\) is found, we may continue Algorithm 2 with \(S^\star \coloneq B\), restricting Phase I to a maximum of six iterations, which ensures that \(G[S^\star]\) is bipartite and \(|S^\star| \ge |B^\star |\).
Finding \(B\). Instead of searching directly for \(B\), we determine the vertices that belong to \((I_1 \cup I_2 \cup I_3) \setminus B\). Let \(P = (I_1 \cup I_2) \setminus B\). Then \(G[P]\) must be isomorphic to one of the nine graphs on at most four vertices listed earlier, and we require \(C^F \cap (I_1 \cup I_2) \subseteq P\). The number of possible \(P\) is \(O((n+m)^2)\), and all can be enumerated within that bound.
For each \(P\), we choose \(P' \subseteq I_3 \setminus B^F\) such that \(C^F \cap I_3 \subseteq P'\) and \(|C^F \cap I_3| \le |P'| \le 2\). If \(|C^F \cap I_3| \ge 1\), there are \(O(n)\) possible subsets \(P'\). If \(C^F \cap I_3 = \emptyset\), up to two vertices in \(I_3 \cap R\) can be selected to form \(P'\). The number of choices satisfies \[1 + |I_3 \cap R| + \frac{|I_3 \cap R|(|I_3 \cap R|-1)}{2} \le 1 + d(v) + d(v)(|R|-1) \le 1 + 2m = O(m).\] For each pair \((P,P')\), we verify in \(O(n+m)\) time whether \((I_1 \cup I_2 \cup I_3) \setminus (P \cup P')\) has greater cardinality than the largest valid \(B\) found so far and still satisfies the required properties. The total complexity is thus \(O((n+m)^4)\).
If no valid \(B\) exists, then \(G \notin (\boldsymbol{2},\boldsymbol{2})\). Otherwise, up to six iterations of Phase I of Algorithm 2 suffice to increase the size of \(S^\star\) until \(|S^\star| \ge |B^\star |\). Hence, the overall complexity of the algorithm is reduced to \(O(n^4 (n+m)^3)\).
Finally, since \(G \in (\boldsymbol{2},\boldsymbol{2})\) if and only if \(\overline{G} \in (\boldsymbol{2},\boldsymbol{2})\), if \(\overline{G}\) has fewer edges than \(G\) (i.e., \(\overline{m} = \binom{n}{2} - m < m\)), it is more efficient to apply the algorithm to \(\overline{G}\) instead, with an additional cost of \(O(n^2)\). We thus obtain the following result.
Theorem 3. It can be determined in \(O(n^4 (n + \min\{m,\overline{m}\})^3)\) time whether a graph \(G = (V,E)\) belongs to the class \((\boldsymbol{2},\boldsymbol{2})\).
Acknowledgments↩︎
Partially supported by CONICET (PIP 11220200100084CO), UBACyT (20020220300079BA and 20020190100126BA), and ANPCyT (PICT-2021-I-A-00755). We would like to thank Eric Brandwein for his valuable comments.