Check whether a given graph is bipartite except for one edge

Question

Given any graph $G=(V,E)$, how to decide if deleting just one of its edges can make it bipartite?

Trivial solution: check for each edge whether deleting it makes the graph bipartite. This is in $O(|E|\cdot(|E|+|V|))$.

Are there more efficient ways?

Answer 1

First, find an odd cycle. Then, try sequentially deleting and re-inserting each of the edges of the cycle, keeping track of whether any of the deletions produces a bipartite graph, using the dynamic bipartiteness testing algorithms from

"Sparsification—A technique for speeding up dynamic graph algorithms". D. Eppstein, Z. Galil, G.F. Italiano, and A. Nissenzweig. J. ACM 44 (5): 669–696, 1997. https://dl.acm.org/doi/abs/10.1145/265910.265914

or

"Randomized fully dynamic graph algorithms with polylogarithmic time per operation". Henzinger and King. J. ACM, 1999. https://dl.acm.org/doi/abs/10.1145/320211.320215

The 1997 paper should give you $O(m + n^{3/2})$ and the 1999 one should give you randomized expected time $O(m\log^3 n)$. There's also a non-random dynamic algorithm from

"Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity". Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. J. ACM 2001. https://dl.acm.org/doi/abs/10.1145/502090.502095

that is probably something like $O(m + n\log^{O(1)} n)$ but they only mention bipartiteness in passing in a single line so I am not entirely sure of what their bounds are. Some of their polylogs have been subsequently improved by other papers but I didn't see bipartiteness listed among the improvements.

Answer 2

The edge to remove must belong to all cycles of odd length. If there are disjoint such cycles, then there are no edge satisfying your assertion.

Notice also that several edge choices may be possible. For instance, if $G$ is a ring with odd number of nodes, then removing any edge makes it bipartite.

Let us say that a graph is almost bipartite if it is not bipartite but removing just one of its edges may make it bipartite, and let us assume that $G$ is not bipartite.

My approach would be to first find a cycle of odd length in $G$, which is in $O(|V|+|E|)$. I would remove its edges from $G$ and check in $O(|V|+|E|)$ if the remaining graph is bipartite. If not, then there are disjoint cycles of odd length, and thus $G$ is not almost bipartite.

If the remaining graph is bipartite, then I would compute in $O(|V|+|E|)$ its two parts $\top$ and $\bot$. Then, the vertices of the cycle are in either $\top$, $\bot$, or $V' = V\setminus(\top\cup\bot)$.

EDIT: if the remaining graph is not connected, then there may be several possible bipartitions into $\top$ and $\bot$ above, and the number of bipartitions may be of the order of magnitude of $|V|$ as illustrated by Dániel G. in the comments. Therefore, another approach is needed.

If $V'$ is empty, then we are done: the edge to remove is the one between two $\top$ or two $\bot$ nodes, if its is unique; otherwise, $G$ is not almost bipartite.

If $V'$ is not empty, then either there is only one sequence of consecutive $V'$ nodes in the cycle of odd length, and any of its edges may be removed to make $G$ bipartite; or there are several such sequences and $G$ is not almost bipartite.

Processing the cycle in this way is in $O(|V|)$, which makes the whole process in $O(|V|+|E|)$, if I am correct.

Answer 3

We seem to lack inspiration here, so let me detail an $O(|V|\cdot(|E|+|V|))$ solution.

Assume there is an odd cycle in $G$; if there is none then $G$ is bipartite. Then, pick any vertex $v$ and consider a BFS tree from it. If an edge exists between two vertices at the same distance from $v$, then we have an odd cycle. Conversely, notice that the existence of an odd cycle implies that such an edge exists too. Therefore, we obtain an odd-length cycle in $O(|E|)$.

Any cycle has at most $|V|$ edges, and if $G$ is bipartite except for one edge then the additional edge is in all odd-length cycles. We therefore try to remove each edge of our odd-length cycle in turn and check if the obtained graph is bipartite, as proposed in the initial question for all edges in $E$. This makes an $O(|V|\cdot(|E|+|V|))$ solution.

But there must be better ways!

Answer 4

There is a linear solution, with a Depth-First Search (DFS), using Tarjan's representation of the graph.

In short, the problem's solution is : run Tarjan's bridge-finding algorithm while also bicoloring the graph and removing the edges incompatible with the coloration you're computing. Once you've done this, find one of the bridges that, upon suppression, allows you to add all the edges you removed. This can be found along the exploration. (see the definition of a bridge and the algorithm in https://en.wikipedia.org/wiki/Bridge_(graph_theory)#Tarjan's_bridge-finding_algorithm)

Tarjan's representation of a DFS

The idea of Tarjan's representation is simple, but very powerful for a lot of graph connectivity problems (and coloration, etc). I haven't found a generic presentation for reference, so here is a short one, along with the vocabulary for this answer.

First, suppose your graph is connex (else, apply to each connected component). You start a depth-first search, and you classify the edges when you encounter them :

• Some edges are connecting the node you're actually in to a node you've never encountered before. Mark them as "down" edges.
• Some edges are connecting the node you're actually in to a node you've already encountered. Mark them as "return" edges.

Now, some very interesting properties happen :

• the "down" edges are a rooted spanning tree of the graph (rooted in the first explored node), representing the recursive calls of the depth-first search.
• if the graph is non-oriented, then the "return" edges are always between a node and one of its ancestors in the spanning tree. Indeed, you have already encountered the node before, but you haven't yet finished enumerating its nodes, so the depth-first search recursive function hasn't returned yet.
• General culture fact : if the graph is oriented, that the "return" edges have more variations (they can go to other branches of the tree, or to children in the tree). These are cool properties to study for other algorithms.

The power of Tarjan's representation lies in these properties, that allow us to send information down and up the recursive calls of the DFS. The solution to this problem works like this.

Algorithm ideas

Computing a first coloration and compatibility of edges

Consider the classic DFS algorithm for computing a bipartition :

• color a node in a color
• recursively color each unseen neighbor in the opposite color

This gives an initial coloration $C_0$. If we look how it acts on the Tarjan representation, we have :

• The nodes are colored according to their depth (modulo 2), so the "down" edges are compatible with the coloration $C_0$
• To check whether a "return" edge is compatible with the coloration $C_0$, we only have to check whether the difference of depth between its ends is odd. If it is even, then both its endpoints have the same color, so this edge is a conflict (and we have found an odd-cycle length). If it is odd, then this edge does not conflict with the coloration.

So now, in one pass, we can generate a coloration along with all the conflicts it creates.

Which edges could be the solution to the problem ?

Now, we have to choose one edge $e$ to remove, and edit the coloration $C_0$ to have a bipartition with a new coloration $C(e)$.

Either we are lucky, and there is only one (or zero) conflicting edge ; then we remove it and call it a day.

Or, we have at least two conflicting edges. Then, we have to remove one of the "down" edges ; indeed, if we don't remove one of those, then the spanning tree imposes the coloration $C_0$ we already had, and there will be a conflict.

When we remove a "down" edge, this will split the spanning tree in two trees. We have to invert the coloration of exactly one of these two trees (once we invert one of the nodes, all the nodes in its tree will have to be inverted as well ; and if we invert both trees, then we've done nothing). By symmetry, let's say we choose to invert the part that does not contain the root (we won't explicitly compute it, so it has no influence on the actual algorithm). For a down edge $e$, this gives the new coloration $C(e)$. We call $M(e)$ the main part of the initial spanning tree which contains the root, and $B(e)$ the branch which does not contain the root.

Now :

• The remaining "down" edges are still compatible with the new coloration $C(e)$
• $(*)$ Let $f$ be a "return" edge that has one end in $M(e)$ and one in $B(e)$, then if it was compatible with $C_0$, it isn't compatible with $C(e)$. Which is impossible. But if $f$ was incompatible with $C_0$, then now it is compatible with $C(e)$.
• $(**)$ Let $g$ be a "return" edge that has both ends in $M(e)$, or both ends in $B(e)$, then its compatibility with $C_0$ is the same as its compatibility with $C(e)$. So, if $e$ is the right edge to remove, then $g$ was compatible with $C_0$.

Translating this in computable properties

Because of $(*)$, if we restrict the graph $G$ to the edges compatible with $C_0$, then $e$ has to be a bridge of this restricted graph $G_r$. If an edge $e$ is a bridge, then removing it and inverting the coloration of $B(e)$ won't break the compatibility of already-compatible edges, because none of them ends up in case $(*)$.

Because of $(**)$, all the edges incompatible with $C_0$ have an end above $e$ and an end below $e$. If an edge $e$ corresponds to these constraints for all the edges that were incompatible with $C_0$, then removing it and inverting the coloration of $B(e)$ will repair the compatibility of all the precedingly incompatible edges, because all of them end up in case (*).

We need both : a $G_r$-bridge, that is part of every path of the incompatible edges (globally, this means that $e$ is part of every odd-length cycle that is elementary along the spanning tree). For the same edge. Let's do this !

Actual algorithm

Ideas

The task is now to find such an edge $e$. All the computation related to this can be done in a single DFS, but to make things clearer we're gonna do several of them, encountering the nodes in the same order.

We run a first DFS algorithm to compute the coloration $C_0$.

Then we remove the edges incompatible with $C_0$, to compute the restricted graph $G_r$.

Then we run a bridge-finding algorithm on $G_r$, to extract all the bridges.

Then, on the Tarjan decomposition, each incompatible return edge $f = v_{bottom} \to v_{top}$ has an end $v_{top}$ which lies in $M(e)$ and an end $v_{bottom}$ which lies in $B(e)$ ; so $v_{top}$ imposes that $e$ is a descendant of $v_{top}$, and $v_{bottom}$ imposes that $e$ is an ascendant of $v_{bottom}$.

This kind of constraints (be a bridge, be lower than all $v_{top}$, be higher than all $v_{bottom}$, be only one edge) are the kind of constraints that are easy to enforce in a DFS.

Implementation

The exact implementation might be tricky, but conceptually you would be asking to each of your descendants in the DFS "what are the constraints you have for me and my ascendants ?", and expecting an answer among :

• I have no constraint
• I need a bridge with a depth at least equal to {some node}, but I have found one in my branch that is OK for me
• I need a bridge with a depth at least equal to {some node} and haven't found one yet
• I have found my bridge in my branch and you can't make me change it
• The constraints are too hard to be solved with only one edge removal

Given such an answer for each of your descendants, and all the return edges of which you are the $v_{bottom}$ (and whether they're compatible or not), and whether the edge you came through is a bridge, you can compute the answer for the node you're actually in. A lot of particular cases to think of, but it'll work.

And of course, don't forget that you can be lucky and maybe the first coloration you found already has one or zero incompatible edges. You have to check that independently.

And run that on each connected component.