a near-bipartite decomposition. If so, then $G$ is near-bipartite and we apply Lemma \[l-2\]. If not, then $G$ is not near-bipartite due to Theorem \[t-yy06\].

We note that the running time of the algorithm in Theorem \[t-p\] is determined by the time it takes to find and process each set $X$ of size $4\leq |X|\leq 5$. This takes $O(n^7)$ time, as checking the existence of a set $X$ takes $O(n^5)$ time using brute force, determining the $2$-neighbour set $A_X$ takes $O(n)$ time and checking if $(A_X,V\setminus A_X)$ is a near-bipartite decomposition takes $O(n^2)$ time.

Near-Bipartiteness for Diameter $3$ {#s-diam3}
===================================

In this section we prove that [Near-Bipartiteness]{} is [[NP]{}]{}-complete for graphs of diameter $3$. In order to prove this, we use a construction of Mertzios and Spirakis [@MS16]. To introduce this construction, we first consider the constraint graph $J$ defined in Figure \[fig:constraint-graph\].

\[lem:constraint-graph\] Let $X$ be a subset of $\{X_1, X_2, X_3\} \subset V(J)$ containing at most two vertices. Then there exists a near-bipartite decomposition $(A,B)$ of $J$ such that, for $1 \leq p \leq 3$, $X_p \in A$ if and only if $X_p \in X$.

Noting the automorphic equivalence of $X_2$ and $X_3$, it is sufficient to consider 