1
$\begingroup$

An edge cut of a graph $G$ induced by a partition of $G$'s vertices into sets $X$ and $Y$ is the set of all edges with one endpoint in $X$ and another endpoint in $Y$.

An edge separator is a set of edges whose removal will increase the number of connected components in the graph.

Note that these are two distinct concepts and cannot be considered equivalent.

An edge separator is not necessarily an edge cut. For example,

For the complete bipartite geaph $K_{3,3}$, a set of any seven edges of $K_{3,3}$ is an edge separator, but a set of any seven edges of $K_{3,3}$ is not an edge cut.

For another exmaple,

enter image description here

The brown edges highlighted in the above Figure represent an edge-separating set, but it is not an edge cut. The set of brown edges on the right is an edge cut.

It is easy to determine whether a set of edges is an edge separator. But how do we determine if a set of edges is an edge cut of a graph? I don't have a good idea yet, but I have a rough idea which is to color the set of vertex-ends of edges under consideration and then see if a partition as defined by the edge cut can be found.

$\endgroup$

1 Answer 1

2
$\begingroup$

As you say, a cut in a graph $G=(V,E)$ is an edge set $C$ with the property that you may partition the vertices of $G$ (let's call the parts $A$ and $B$) in such a way that $C$ is exactly the set of edges with one end in $A$ and the other in $B$. This implies that the subgraph $H=(V,C)$ is bipartite with color classes $A$ and $B$. However, it is not enough to check that $H$ is bipartite, as this may disregard vertices that should be on the same side.

A good trick to use in a situation like this is contraction, i.e. we shrink every component of $\overline{H}=(V,E-C)$ down to a single vertex and let the edges in $C$ go between these instead. A simple way to achieve this is to find all the components of $\overline{H}$ (just run your favorite search algorithm on the graph until all vertices are seen), and build a new graph $\widetilde{H}$ where:

  • Each vertex corresponds to a component of $\overline{H}$
  • Each edge corresponds to an edge in $C$, with the endpoints corresponding to the components of endpoints of the original edge
  • Multiple edges and loops are allowed

Now, $C$ is a cut in $G$ if and only if $\widetilde{H}$ is bipartite and has no loops.

I made the graphs $\widetilde{H}$ corresponding to the graphs in your figure to make it a bit more clear:

enter image description here enter image description here

You should be able to do all of this in $O(|V|+|E|)$ time.

$\endgroup$
4
  • $\begingroup$ Why can't there be loops in $ \widetilde{H}$ when $C$ is a cut? If one component of $G−C$ is a cut edge, won't it create a loop when contracted the component? $\endgroup$
    – licheng
    Commented Feb 26, 2023 at 3:34
  • $\begingroup$ Sorry, it seems that no new self-loop is created during the contraction process. Was the self-loop allowed in your graph $G$ itself? $\endgroup$
    – licheng
    Commented Feb 26, 2023 at 8:03
  • 1
    $\begingroup$ I'm sorry, I see the wording was a bit off there. A loop corresponds an edge that goes between two vertices in the same component in $G$. Strictly speaking, if one of the edges make a loop, then you instantly know that $C$ is not a cut, as it should only contain edges that run between different components of $G$. So it would maybe be better if I said that you disallow loops since if you encounter them you instantly know that you are dealing with a NO-instance. $\endgroup$
    – Highheath
    Commented Feb 26, 2023 at 8:25
  • 1
    $\begingroup$ Thank you very much for your reply. The self-loops in the connected components of G-C were not mentioned to be handled (perhaps they can be simply deleted). Overall, the algorithm you provided is undoubtedly correct. $\endgroup$
    – licheng
    Commented Feb 26, 2023 at 8:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.