constraint graph $J$ and the only rows that contain more than one such vertex are those in the variable block.

For an instance $\phi$ of [$3$-Sat]{}, $H_\phi$ has diameter $3$.

Note that in [@MS16], Lemma 2 proves the bound on the diameter for a graph that is a spanning subgraph of $H_\phi$ which is, of course, sufficient for an upper bound for the diameter of $H_\phi$ and it is easy to see that the diameter is not less than $3$. We note also that $H_\phi$ does not contain any triangles or any vertices that are siblings (two vertices are siblings if the neighbourhood of one is a subset of the neighbourhood of the other) so [Near-Bipartiteness]{} is also [[NP]{}]{}-complete for such instances.

\[thm:diam3\] [Near-Bipartiteness]{} is [[NP]{}]{}-complete for graphs of diameter at most $3$.

We prove that [$3$-Sat]{} can be polynomially-reduced to [Near-Bipartiteness]{} by showing that $\phi$ is satisfiable if and only if $H_\phi$ has a near-bipartite decomposition $(A,B)$.

($\Rightarrow$) Suppose that $\phi$ has a satisfying assignment. Let $v_0$ be in $A$, and let the vertices of all the dominating blocks be in $B$. If the variable $v_i$ is true, then let $B$ contain all the true vertices of row $i$ 