---
abstract: 'The [Near-Bipartiteness]{} problem is that of deciding whether or not the vertices of a graph can be partitioned into sets $A$ and $B$, where $A$ is an independent set and $B$ induces a forest. The set $A$ in such a partition is said to be an independent feedback vertex set. Yang and Yuan proved that [Near-Bipartiteness]{} is polynomial-time solvable for graphs of diameter $2$ and [[NP]{}]{}-complete for graphs of diameter $4$. We show that [Near-Bipartiteness]{} is [[NP]{}]{}-complete for graphs of diameter $3$, resolving their open problem. We also generalise their result for diameter $2$ by proving that even the problem of computing a minimum independent feedback vertex is polynomial-time solvable for graphs of diameter $2$.'
author:
- Marthe Bonamy
- 'Konrad K. Dabrowski'
- Carl Feghali
- |
    \
    Matthew Johnson
- Daniël Paulusma
bibliography:
- 'mybib.bib'
title: |
    Independent Feedback Vertex Sets for\
    Graphs of Bounded Diameter[^1]
---

Introduction
============

A graph is [*near-bipartite*]{} if its vertex set can be partitioned into sets $A$ and $B$, where $A$ is an independent set and $B$ induces a forest. The set $A$ is said to be an [*independent feedback vertex set*]{} and the pair $(A,B)$ is said to be a [*near-bipartite decomposition*]{}. This leads to the following two related decision problems.

[.99]{} <span style="font-variant:small-caps;">[Near-Bipartiteness]{}</span>\

  ----------------- ----------------------------------------------------------------------------------------
    *    Instance:* [a graph $G$.]{}
        *Question:* [is $G$ near-bipartite (that is, does $G$ have an independent feedback vertex set)?]{}
  ----------------- ----------------------------------------------------------------------------------------

[.99]{} <span style="font-variant:small-caps;">[Independent Feedback Vertex Set]{}</span>\

  ----------------- ---------------------------------------------------------------------------
    *    Instance:* [a graph $G$ and an integer $k\geq 0$.]{}
        *Question:* [does $G$ have an independent feedback vertex set of size at most $k$?]{}
  ----------------- ---------------------------------------------------------------------------

Setting $k=n$ shows that the latter problem is more general than the first problem. Thus, if [Near-Bipartiteness]{} is [[NP]{}]{}-complete for some graph class, then so is [Independent Feedback Vertex Set]{}, and if [Independent Feedback Vertex Set]{} is polynomial-time solvable for some graph class, then so is [Near-Bipartiteness]{}.

Note that every near-bipartite graph is $3$-colourable, that is, its vertices can be coloured with at most three colours such that no two adjacent vertices are coloured alike. The problems [$3$-Colouring]{} [@Lo73] and [Near-Bipartiteness]{} [@BLS98] (and thus [Independent Feedback Vertex Set]{}) are [[NP]{}]{}-complete. However, their complexities do not necessarily coincide on special graph classes. Grötschel, Lovász and Schrijver [@GLS84] proved that [Colouring]{} is polynomial-time solvable for perfect graphs even if the permitted number of colours $k$ is part of the input. However, Brandstädt et al. [@BBKNP13] proved that [Near-Bipartiteness]{} remains [[NP]{}]{}-complete for perfect graphs. The same authors also showed that [Near-Bipartiteness]{} is polynomial-time solvable for $P_4$-free graphs.

Yang and Yuan [@YY06] proved that [Near-Bipartiteness]{} also remains [[NP]{}]{}-complete for graphs of maximum degree $4$. To complement their hardness result, Yang and Yuan [@YY06] showed that every connected graph of maximum degree at most $3$ is near-bipartite except the complete graph $K_4$ on four vertices. This also follows from a more general result of Catlin and Lai [@CL95]. Recently we gave a linear-time algorithm for finding an independent feedback vertex set in a graph of maximum degree at most $3$ [@BDFJP17], and also proved that [Near-Bipartiteness]{} is [[NP]{}]{}-complete even for line graphs of maximum degree $4$ [@BDFJP17b]. It is also known that [Near-Bipartiteness]{} is [[NP]{}]{}-complete for planar graphs; this follows from a result of Dross, Montassier and Pinlou [@DMP16]; see the arXiv version of [@BDFJP17] for details.

Tamura, Ito and Zhou [@TIZ15] proved that [Independent Feedback Vertex Set]{} is [[NP]{}]{}-complete for planar bipartite graphs of maximum degree $4$ (note that [Near-Bipartiteness]{} is trivial for bipartite graphs). They also proved that [Independent Feedback Vertex Set]{} is linear-time solvable for graphs of bounded treewidth, chordal graphs and $P_4$-free graphs (the latter result generalising the result of [@BBKNP13] for [Near-Bipartiteness]{} on $P_4$-free graphs). In [@BDFJP17b] we proved that finding a minimum independent feedback vertex set is polynomial-time solvable even for $P_5$-free graphs. We refer to [@AGSS16; @MPRS12] for FPT algorithms with parameter $k$ for finding an independent feedback vertex set of size at most $k$.

The [*distance*]{} between two vertices $u$ and $v$ in a graph $G$ is the length (number of edges) of a shortest path between $u$ and $v$. The [*diameter*]{} of a graph $G$ is the maximum distance between any two vertices in $G$. In addition to their results for graphs of bounded maximum degree, Yang and Yuan [@YY06] proved that [Near-Bipartiteness]{} is polynomial-time solvable for graphs of diameter at most $2$ and [[NP]{}]{}-complete for graphs of diameter at most $4$. They asked the following question, which was also posed by Brandstädt et al. [@BBKNP13]:

[*What is the complexity of [Near-Bipartiteness]{} for graphs of diameter $3$?*]{}

[**Our Results.**]{} We complete the complexity classifications of [Near-Bipartiteness]{} and [Independent Feedback Vertex Set]{} for graphs of bounded diameter. In particular, we prove that [Near-Bipartiteness]{} is [[NP]{}]{}-complete for graphs of diameter $3$, which answers the above question. We also prove that [Independent Feedback Vertex Set]{} is polynomial-time solvable for graphs of diameter $2$. This generalises the result of Yang and Yuan [@YY06] for [Near-Bipartiteness]{} restricted to graphs of diameter $2$.

\[t-main\] Let $k\geq 0$ be an integer.

(i) If $k\leq 2$, then [Independent Feedback Vertex Set]{} (and thus [Near-Bipartiteness]{}) is polynomial-time solvable for graphs of diameter $k$.\

(ii) If $k\geq 3$, then [Near-Bipartiteness]{} (and thus [Independent Feedback Vertex Set]{}) is [[NP]{}]{}-complete for graphs of diameter $k$.

We prove Theorem \[t-main\] (i) in Section \[s-poly\]. Yang and Yuan [@YY06] proved their result for [Near-Bipartiteness]{} by giving a polynomial-time verifiable characterisation of the class of near-bipartite graphs of diameter $2$. We use their characterisation as the starting point for our algorithm for [Independent Feedback Vertex Set]{}. In fact our algorithm not only solves the decision problem but even finds a minimum independent feedback vertex set in a graph of diameter $2$.

We prove Theorem \[t-main\] (ii) in Section \[s-diam3\] by using a construction of Mertzios and Spirakis [@MS16], which they used to prove that [$3$-Colouring]{} is [[NP]{}]{}-complete for graphs of diameter $3$. The outline of their proof is straightforward: a reduction from [$3$-Satisfiability]{} that constructs, for any instance $\phi$, a graph $H_\phi$ that is $3$-colourable if and only if $\phi$ is satisfiable. We reduce [$3$-Satisfiability]{} to [Near-Bipartiteness]{} for graphs of diameter $3$ using the same construction, that is, we show that $H_\phi$ is near-bipartite if and only if $\phi$ is satisfiable. As such, our result is an observation about the proof of Mertzios and Spirakis, but, owing to the intricacy of $H_\phi$, this observation is non-trivial to verify. In Section \[s-diam3\] we therefore repeat the construction and describe our reduction in detail, though we rely on [@MS16] where possible in the proof.

Independent Feedback Vertex Set for Diameter $2$ {#s-poly}
================================================

In this section we show how to compute a minimum independent feedback vertex set of a graph of diameter $2$ in polynomial time. As mentioned, our proof relies on a known characterisation of near-bipartite graphs of diameter $2$ [@YY06]. In order to explain this characterisation, we first need to introduce some terminology.

Let $G=(V,E)$ be a graph and let $X\subseteq V$. Then the [*$2$-neighbour set*]{} of $X$, denoted by $A_X$, is the set that consists of all vertices in $V\setminus X$ that have at least two neighbours in $X$. A set $I\subseteq V$ is [*independent*]{} if no two vertices of $I$ are adjacent. For $u\in V$, we let $G-u$ denote the graph obtained from $G$ after deleting the vertex $u$ (and its incident edges). A graph is [*complete bipartite*]{} if its vertex set can be partitioned into two independent sets $S$ and $T$ such that there is an edge between every vertex of $S$ and every vertex of $T$. If $S$ or $T$ has size $1$, the graph is also called a [*star*]{}.

\[t-yy06\] A graph $G=(V,E)$ of diameter $2$ is near-bipartite if and only if one of the following two conditions holds:

(i) \[cond:i\]there exists a vertex $u$ such that $G-u$ is bipartite; or

(ii) \[cond:ii\]there exists a set $X$, $4\leq |X|\leq 5$, such that $(A_X,V\setminus A_X)$ is a near-bipartite decomposition.

As noted in [@YY06], Theorem \[t-yy06\] can be used to solve [Near-Bipartiteness]{} in polynomial time for graphs of diameter $2$, as conditions \[cond:i\] and \[cond:ii\] can be checked in polynomial time. However, Theorem \[t-yy06\] does not tell us how to determine the size of a minimum independent feedback vertex set.

In order to find a minimum independent feedback vertex set, we will distinguish between the two cases of Theorem \[t-yy06\]. This leads to two corresponding lemmas.

\[l-1\] Let $G=(V,E)$ be a near-bipartite graph of diameter $2$ that contains a vertex $u$ such that $G-u$ is bipartite. Then it is possible to find a minimum independent feedback vertex set of $G$ in polynomial time.

We can partition $V\setminus\{u\}$ into four independent sets $S_1$, $S_2$, $T_1$, $T_2$ (some of which might be empty) such that

(i) \[prop:i\]$S_1\cup S_2$ and $T_1\cup T_2$ form bipartition classes of $G-u$;

(ii) \[prop:ii\]$u$ is adjacent to every vertex of $S_1\cup T_1$; and

(iii) \[prop:iii\]$u$ is non-adjacent to every vertex of $S_2\cup T_2$.

Moreover, as $G$ has diameter $2$, it follows that given a vertex of $S_2$ (respectively, $T_2$) and a vertex of $T_1\cup T_2$ (respectively, $S_1\cup S_2$), these two vertices must either be adjacent or have a common neighbour. As the latter is not possible, we deduce that

(i) \[prop:iv\]every vertex of $S_2$ is adjacent to every vertex of $T_1\cup T_2$, and every vertex of $T_2$ is adjacent to every vertex of $S_1\cup S_2$ (see also  \[fig:STu\]).

=\[circle,draw=black, fill=black, minimum size=5pt, inner sep=1pt\] =\[draw,black\]

///in [ (0,-2)/T/1/below, (0,2)/S/1/above, (5,-2)/T/2/below, (5,2)/S/2/above]{}

(0.6,-0.4) rectangle (3.4,0.4); (1) at (1,0) ; (2) at (2,0) ; (3) at (3,0) ; at (2,0) [$\name_\number$]{};

\(u) at (0,0) ;

/in [1/1,1/2,2/1,2/2,1/3,2/3,3/3,3/2,3/1]{} [ (S1) – (T2) – (S2) – (T1); ]{}

in [1,2,3]{} [ (S1) – (u) – (T1); (S2) – (u) – (T2); ]{}

at (u) [$u$]{};

A (not necessarily proper) $2$-colouring of the vertices of a graph is *good* if the vertices coloured $1$ form an independent set and the vertices coloured $2$ induce a forest. The set of vertices coloured $1$ in a good $2$-colouring is said to be a *$1$-set* and is, by definition, an independent feedback vertex of $G$. A good $2$-colouring of $G$ is [*optimal*]{} if its $1$-set is of minimum possible size among all good $2$-colourings. Our algorithm colours vertices one by one with colour $1$ or $2$ to obtain a number of good $2$-colourings. We will establish that our approach ensures that at least one of our good $2$-colourings is optimal. Therefore, as our algorithm finds different good $2$-colourings, it only needs to remember the smallest $1$-set seen so far. We note that $G$ certainly has good $2$-colourings as, for example, we can let either $S_1\cup S_2$ or $T_1\cup T_2$ be the set of vertices coloured $1$.

We say that an edge is a [*$1$-edge*]{} if both its end-points have colour $1$ and say that a cycle of $G$ is a [*$2$-cycle*]{} if all its vertices have colour $2$. Our algorithm will consist of a number of branches depending on the way we will colour the vertices of $G$. Whenever we detect a $1$-edge or a $2$-cycle in a branch, we can discard the branch as we know that we are not going to generate a good $2$-colouring. Before we describe our algorithm, we first prove the following claim. Here, we say that an independent set $I$ is a [*twin-set*]{} if every vertex of $I$ has the same neighbourhood.

[[[*Claim .* ]{}]{}[*\[clm:1\]Let $I$ be a twin-set. In every optimal $2$-colouring, at least $|I|-1$ vertices of $I$ obtain the same colour.*]{}\
]{} We prove Claim \[clm:1\] as follows. If $|I|=1$, the claim is trivial. Suppose $|I|\geq 2$ and let $J$ be the neighbourhood of the vertices of $I$. Note that $J$ is non-empty since $|I|\geq 2$ and $G$ is connected. Let $c$ be an optimal $2$-colouring of $G$. If $c$ gives colour $1$ to a vertex of $J$, then every vertex of $I$ must receive colour $2$. Now suppose that $c$ gives colour $2$ to every vertex of $J$. If $|J|=1$, then $c$ colours every vertex of $I$ with colour $2$, as doing this will not create a $2$-cycle. If $|J|\geq 2$ then, in order to avoid a $2$-cycle, at least $|I|-1$ vertices of $I$ must be coloured $1$. This proves Claim \[clm:1\].

By \[prop:i\], \[prop:iii\], \[prop:iv\], we find that $S_2$ and $T_2$ are twin-sets. Let $Z$ be the set of isolated vertices in the subgraph of $G$ induced by $S_1\cup T_1$. Then by \[prop:i\], \[prop:ii\], \[prop:iv\], the neighbourhood of every vertex in $Z\cap S_1$ (respectively, $Z\cap T_1$) is $T_2\cup \{u\}$ (respectively, $S_2\cup \{u\}$). So $Z\cap S_1$ and $Z\cap T_1$ are twin-sets.

We choose one vertex from each non-empty set in $\{S_2,T_2,Z\cap S_1,Z\cap T_1\}$ and let $W$ be the set of chosen vertices. Note that the choice of the vertices in $W$ can be done arbitrarily, since all four of these sets are twin-sets. We now branch by giving all vertices in $S_2 \setminus W$ the same colour, all vertices in $T_2 \setminus W$ the same colour, all vertices in $(Z\cap S_1)\setminus W$ the same colour and all vertices in $(Z\cap T_1)\setminus W$ the same colour. We then branch by colouring the at most four vertices of $W$ with every possible combination of colours. Hence the total number of branches is at most $2^8$. We discard any branch that yields a $1$-edge or $2$-cycle. Let $S_1' = S_1 \setminus Z$ and $T_1'=T_1 \setminus Z$. For each remaining branch we try to colour the remaining vertices of $G$, which are all in $S_1'\cup T_1'\cup \{u\}$, and keep track of any minimum $1$-set found. In the end we return a $1$-set of minimum size (recall that $G$ has at least two $1$-sets).

For any remaining branch we do as follows. We first give colour $1$ to $u$. Then every vertex of $S_1'\cup T_1'$ must get colour $2$. If this does not yield a $1$-edge or $2$-cycle, we obtain a $1$-set, which we remember if it is the smallest one found so far.

We now give colour $2$ to $u$. If $u$ was the only remaining vertex, we check for the presence of a $1$-edge or a $2$-cycle, and if none is present, we remember the $1$-set found if it is the smallest one found so far. Otherwise, we let $D_1,\ldots,D_r$ for some integer $r\geq 1$ be the connected components of the (bipartite) graph induced by $S_1'\cup T_1'$. As these vertices do not belong to $Z$, each $D_i$ contains at least one edge. Moreover, each $D_i$ is bipartite. For $i \in \{1,\ldots,r\}$, we denote the two non-empty bipartition classes of $D_i$ by $D_i^1$ and $D_i^2$ such that $|V(D_i^1)|\leq |V(D_i^2)|$. The following claim is crucial.

[[[*Claim .* ]{}]{}[*\[clm:2\]For $i\in\{1,\ldots,r\}$, we must either colour all vertices of $D_i^1$ with colour $1$ and all vertices of $D_i^2$ with colour $2$, or vice versa.*]{}\
]{} We prove Claim \[clm:2\] as follows. Suppose that $D_i^1$ contains a vertex with the same colour as a vertex of $D_i^2$. As $D_i$ is connected and bipartite, this means that $D_i$ contains an edge $vw$ whose end-vertices are either both coloured $1$ or coloured $2$. In the first case, we obtain a $1$-edge. In the second case the vertices $u$, $v$ and $w$ form a $2$-cycle in $G$. Hence we must use colours $1$ and $2$ for different partition classes of $D_i$. This proves Claim \[clm:2\].

We now proceed as follows. First suppose that $S_2 \cup T_2$ is non-empty. If we coloured a vertex in $S_2$ (respectively $T_2$) with colour $1$, then every vertex in $T_1'$ (respectively $S_1'$) must be coloured $2$ and therefore every vertex in $S_1'$ (respectively $T_1'$) must be coloured $1$ by Claim \[clm:2\]. Again, in this case we discard the branch if a $1$-edge or $2$-cycle is found; otherwise we remember the corresponding $1$-set if it is the best set found so far. In every other case, we must have coloured every vertex of non-empty set $S_2\cup T_2$ with colour $2$. Without loss of generality, assume that there is a vertex $s \in S_2$ that is coloured $2$. Then at most one vertex of $T_1'$ may have colour $2$, as otherwise we obtain a $2$-cycle by involving the vertices $s$ and $u$. We branch by guessing this vertex and then colouring it either $1$ or $2$, while assigning colour $1$ to all other vertices of $T_1'$. Then the only vertices with no colour yet are in $S_1'$, but their colour is determined by the colours of the vertices in $T_1'$ due to Claim \[clm:2\].

We are left to deal with the case where $S_2\cup T_2=\emptyset$. Claim \[clm:2\] tells us that we must either give every vertex of $D_i^1$ colour $1$ and every vertex of $D_i^2$ colour $2$, or vice versa. For $i \in \{1,\ldots,r\}$ we give colour $1$ to every vertex of every $D_i^1$; as $|V(D_i^1)|\leq |V(D_i^2)|$, this is the best possible good $2$-colouring for this branch.

The correctness of our algorithm follows from the fact that we distinguish all possible cases and find a best possible good $2$-colouring (if one exists) in each case. Note that it takes polynomial time to find the sets $S_1$, $S_2$, $T_1$ and $T_2$. Moreover, the number of branches is $O(n)$ and each branch can be processed in polynomial time, as we only need to search for a $1$-edge or $2$-cycle. Hence our algorithm runs in polynomial time.

\[l-2\] Let $G=(V,E)$ be a near-bipartite graph of diameter $2$ that contains no vertex $u$ such that $G-u$ is bipartite. Then it is possible to find a minimum independent feedback vertex of $G$ in polynomial time.

As $G$ is near-bipartite, it has an independent feedback vertex set. Let $A$ be a minimum independent feedback vertex set. We claim that $G$ contains a set of vertices $X$ of size $4\leq |X|\leq 5$ such that $A_X=A$. This would immediately give us a polynomial-time algorithm. Indeed, it would suffice to check, for every set $X$ of size $4\leq |X|\leq 5$, whether $(A_X,V\setminus A_X)$ is a near-bipartite decomposition and to return a set $A_X$ of minimum size that satisfies this condition. This takes polynomial time.

To prove the above claim we will follow the same line of reasoning as in the proof of Theorem \[t-yy06\] However, our arguments are slightly different, as we need to prove a stronger statement.

Let $B=V\setminus A$ and let $F$ be the subgraph of $G$ induced by $B$. By definition, $F$ is a forest, so all of its connected components are trees.

We will first consider the case where $F$ has a connected component $T$ of diameter at least $3$. Let $P$ be a longest path in the tree $T$ on vertices $v_1,\ldots,v_p$ in that order. As $T$ has diameter $3$, we find that $p\geq 4$. If $p\leq 5$, then we let $X=\{v_1,\ldots,v_p\}$. If $p\geq 6$, then we let $X=\{v_1,v_2,v_{p-1},v_p\}$. We will show that $A=A_X$. Let $u\in A$. As $G$ has diameter $2$ and $A$ is an independent set, $u$ is adjacent to $v_1$ or to a neighbour $v^*$ of $v_1$ in $B$. In the latter case, if $v^*\neq v_2$ then $v^*$ must have a neighbour in $\{v_2,\ldots,v_p\}$, otherwise we have found a path that is longer than $P$, but in this case $B$ contains a cycle, a contradiction. Hence, $u$ has at least one neighbour in $\{v_1,v_2\}$, and similarly, $u$ has at least one neighbour in $\{v_{p-1},v_p\}$. So $A\subseteq A_X$. Now suppose $u\in A_X$. Note that $u\neq v_3$ due to our choice of $X$. Then the subgraph of $G$ induced by $V(P)\cup \{u\}$ contains a cycle. Hence $u$ must belong to $A$. So $A_X\subseteq A$. We conclude that $A=A_X$.

We now consider the case where every connected component of $F$ has diameter at most $2$. Such components are either isolated vertices or stars (we say that the latter components are [*star-components*]{} and that their non-leaf vertex is the [*star-centre*]{}; if such a component consists of a single edge, we arbitrarily choose one of them to be the star-centre). If $F$ contains no star-components, then $G$ is bipartite and therefore $G-u$ is bipartite for every vertex $u$, a contradiction. If $F$ contains exactly one star-component, then by choosing $u$ to be the star-centre we again find that $G-u$ is bipartite. Hence $F$ contains at least two star-components $D_1$ and $D_2$. For $i=1,2$, let $v_i$ be the star-centre and let $w_i$ be a leaf in $D_i$.

We choose $X=\{v_1,v_2,w_1,w_2\}$ and show that $A=A_X$. Let $u\in A$. As $G$ has diameter $2$ and $A$ is an independent set, $u$ is either adjacent to $w_1$ or to a neighbour of $w_1$ in $B$. If this neighbour is not $v_1$, then $D_1$ is not a star-component, a contradiction. Hence, $u$ has at least one neighbour in $\{v_1,w_1\}$, and similarly, $u$ has at least one neighbour in $\{v_2,w_2\}$. So $A\subseteq A_X$. Now suppose $u\in A_X$. Then $X\cup \{u\}$ induces either a connected subgraph of $G$ that contains both $D_1$ and $D_2$ (and is therefore not a star-component) or a subgraph with a cycle. Hence $u$ must belong to $A$. So $A_X\subseteq A$. We conclude that $A=A_X$. This completes the proof of our claim and thus the proof of the lemma.

We are now ready to prove the main result of this section.

\[t-p\] The problem of finding a minimum independent feedback vertex set of a graph of diameter $2$ can be solved in polynomial time.

Let $G$ be an $n$-vertex graph of diameter $2$. We first check in polynomial time whether $G$ contains a vertex $u$ such that $G-u$ is bipartite. If so, then we apply Lemma \[l-1\]. If not, then we check in polynomial time whether $G$ contains a set $X$ of size $4\leq |X|\leq 5$ such that $(A_X,V\setminus A_X)$ is 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 the following two cases. If $X$ is a subset of $\{X_1, X_2\}$, let $A=X \cup \{Y_6,Y_7\}$. If $X = \{X_2,X_3\}$, let $A= \{X_2,X_3,Y_4\}$.

Notice that there is no near-bipartite decomposition of $J$ with $\{X_1,X_2,X_3\} \subseteq A$. Combined with the above lemma, this gives an idea of how this will be used later. The vertices $X_1$, $X_2$ and $X_3$ will represent literals in a clause of an instance of [$3$-Sat]{} and membership of $A$ will indicate that a literal is false: thus $A$ can be extended to a near-bipartite decomposition except when every literal is false. (In [@MS16], a weaker result was shown: one can always find a $3$-colouring of $J$ such that members of a chosen *proper* subset of $\{X_1, X_2, X_3\}$ belong to the same class and excluded members do not belong to that class.)

Let $\phi$ be an instance of [$3$-Sat]{} with $m$ clauses $C_1, \ldots, C_m$ and $n$ variables $v_1,\ldots,v_n$. We may assume that each clause has three distinct literals. For a clause $C_k$ in $\phi$, we describe a *clause graph* ${\mathcal C}^k$, illustrated within Figure \[fig:hphi\]. We think of ${\mathcal C}^k$ as an array of $n+5m+1$ rows and eight columns. In each row except the last, every (row,column) position contains exactly two vertices, which we refer to as the *true vertex* and the *false vertex*, and we say that these two vertices are *mates*. The first $n$ rows form the *variable block* of the graph and we think of row $i$ as representing the variable $v_i$. The next $5m$ rows are made up of $m$ *clause blocks* ${\mathcal C}^{k,1}, {\mathcal C}^{k,2}, \ldots, {\mathcal C}^{k,m}$, each of five rows. Every true vertex of the variable and clause blocks is joined by an edge to every false vertex in the same row except its mate. Hence the vertices of each row induce a complete bipartite graph minus a matching. In the final row, each column contains a single vertex, and each of these vertices is joined by an edge to every other vertex in the same column. We call this row the *dominating block*. We complete the definition of the clause graph by describing how we add further edges so that it contains the constraint graph $J$ as an induced subgraph. Let the literals of $C_k$ be $x_{\ell_1},x_{\ell_2},x_{\ell_3}$. We choose vertices from the first three columns of the variable block of ${\mathcal C}^k$ that we will denote $X_1^k, X_2^k, X_3^k$ to represent the literals. If $x_{\ell_p}$ is the variable $v_i$, then we choose as $X_p^k$ a vertex from row $i$ and column $p$, and choose the true vertex if the literal is positive and the false vertex if the literal is a negated variable. For $p \in \{4,\ldots,8\}$, let $Y_p^k$ be the true vertex from the $(p-3)$th row and $p$th column of the clause block ${\mathcal C}^{k,k}$. Finally add the ten edges $\{ X_1^kY_4^k, X_2^kY_5^k, X_2^kY_8^k, X_3^kY_6^k, X_3^kY_7^k, Y_4^kY_5^k, Y_4^kY_6^k, Y_5^kY_7^k, Y_6^kY_8^k, Y_7^kY_8^k\}$ so that $\{X_1^k,X_2^k,X_3^k, Y_4^k, Y_5^k,Y_6^k,Y_7^k,Y_6^k\}$ induces the constraint graph $J$.

=\[circle,draw=black, fill=black, minimum size=5pt, inner sep=1pt\] =\[draw,black\]

We now define the graph $H_\phi$. It contains:

-   the disjoint union of clause graphs ${\mathcal C}^k$, $1 \leq k \leq m$ (we think of the clause graphs as being arranged side-by-side, so that they form an array of $n+5m+1$ rows and $8m$ columns),

-   edges from each true vertex of each clause graph to each false vertex in the same row of other clause graphs, and

-   an additional vertex $v_0$ joined to each vertex in the dominating block of each clause graph.

Note that each column of $H_\phi$ contains exactly one vertex that is in a 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$ of the variable blocks of each clause graph. Otherwise let $B$ contain the false vertices. In each case, let $A$ contain the mates of these vertices. Consider the constraint graph that is an induced subgraph of each clause graph. The vertices $X_1$, $X_2$ and $X_3$ have been assigned to either $A$ or $B$ with at most two, representing false literals, belonging to $A$. By Lemma \[lem:constraint-graph\], we can assign the remaining vertices of the subgraph (which are all true vertices of clause blocks) to $A$ and $B$ such that on the subgraph they form a near-bipartite decomposition. When we assign a true vertex of a clause block to $A$ or $B$, we assign all other true vertices in the same row of $H_\phi$ to the same set and assign their mates to the other set. As each row of the clause blocks contains only one vertex in a constraint graph, this process assigns every vertex in $H_\phi$ to exactly one of $A$ and $B$, and we have assigned every vertex of $H_\phi$ to $A$ or $B$.

It is immediately clear that $A$ is an independent set. We must show that $B$ contains no cycles. We know that $B$ contains all the vertices of the dominating blocks and, in each row, either all the true vertices or all the false vertices. Thus if $B$ contains a cycle then all the vertices of the cycle belong to the same clause graph (the only edges going between distinct clause graphs are those joining true vertices to false vertices in the same row). Let $G_B$ be a subgraph of a clause graph induced by vertices of $B$. Then each true and false vertex not in the constraint graph has degree $1$ (due to the edge joining it to the dominating block), and each vertex in the dominating block has at most one neighbour with degree more than $1$ (since it only has one neighbour in the constraint graph). Thus if $G_B$ contains a cycle then it belongs to the constraint graph, contradicting how $A$ and $B$ were chosen.

($\Leftarrow$) Suppose $A$ and $B$ form a near-bipartite decomposition of $H_\phi$. Then $B$ can be decomposed into two independent sets, and these, along with $A$, can be considered a $3$-colouring. In [@MS16 Theorem 5], it is shown that if $H_\phi$ has a $3$-colouring, then $\phi$ is satisfiable.

Conclusions {#s-con}
===========

We completed the computational complexity classifications of [Near-Bipartiteness]{} and [Independent Feedback Vertex Set]{} for graphs of diameter $k$ for every integer $k\geq 0$. We showed that the complexity of both problems jumps from being polynomial-time solvable to [[NP]{}]{}-complete when $k$ changes from $2$ to $3$.

We recall that near-bipartite graphs are $3$-colourable. Interestingly, the complexity of [$3$-Colouring]{} for graphs of diameter $k$ has not yet been settled, as there is one remaining case left, namely when $k=2$. This is a notorious open problem, which has been frequently posed in the literature (see, for example, [@BKM12; @BFGP13; @MS16; @Pa15]). We note that the approach of solving [Near-Bipartiteness]{} and [Independent Feedback Vertex Set]{} for graphs of diameter $2$ does not work for [$3$-Colouring]{}. For instance, we cannot bound the size of the set $X$ in Lemma \[l-2\] if we drop the condition that the union of two colour classes must induce a forest.

[^1]: This paper received support from EPSRC (EP/K025090/1), London Mathematical Society (41536), the Leverhulme Trust (RPG-2016-258) and Fondation Sciences Mathématiques de Paris. The hardness result (Theorem \[thm:diam3\]) of this paper has been announced in an extended abstract of the Proceedings of MFCS 2017 [@BDFJP17].
