all_node_cuts returns incorrect cuts

[ebehner]

The function all_node_cuts returns node cut-sets for the K2 (complete graph with two nodes), but there exist no.

Current Behavior

Consider the following graph, consisting of two nodes connected by an edge:

graph = nx.Graph()
graph.add_edge(1,2)
list(all_node_cuts(graph)
>>> [{1}, {2}]

This graph has no node cut-sets because removing any vertex does not increase the number of connected components

Expected Behavior

Return no node cut-sets:

graph = nx.Graph()
graph.add_edge(1,2)
list(all_node_cuts(graph)
>>> []

Steps to Reproduce

The above example

Environment

Python version: 3.10.10
NetworkX version: 2.6.3

[navyagarwal]

I think this issue has to do with complete graphs in general, because for a complete graph with n nodes, the connectivity is n-1 which is the size of every node cut-set.

Node cut-set of an undirected graph G is the set of nodes, that if removed, would break G into two or more connected components.

For a K-N graph, we will have to remove n-1 nodes that will break the graph into two components - one with a single node and another with no nodes.

If we assume an empty graph to be a component by itself, then perhaps the output of all_node_cuts is valid, else maybe an exception can be raised whenever a complete graph is passed in.

[dschult]

TLDR; Issue #3025 points out a few bugs which were fixed in #3039 They left the complete graph case, but it seems thatis not handled correctly.

Looking through the blame history of this function, it seems that bug reports such as #1875 have been fixed by adding extra code to handle those cases rather than fixing the underlying algorithm. Special code for e.g. cycles was also added but has since been removed without removing the code for complete graphs. I'm not sure why this approach was taken. Was the underlying algorithm investigated and found to be unable to handle those cases? How do we know the underlying algorithm is correct? I've been playing with it and it seems to work fine.

The tests use node_connnectivity to give the size of the minimal cutset. The doc_string for node_connectivity mentions that the connectivity is the number of nodes that need to be removed so that the graph is disconnected or the trivial graph (trivial graph is one node, no edges). So, I believe the author considered a node cut-set to be the nodes which when removed leave a disconnected or trivial graph.

By the definitions of node cut or vertex cut that I have found, it only is a cut if the resulting graph is disconnected. That is different from what is implemented here I think.

But, are there graphs that are not complete graphs that have "no node cut-set". That is, there is no set of nodes which when removed leave the graph disconnected? I don't think so... because if you consider an edge that isn't present in the graph, then removing all but the two nodes on either side of the missing edge will leave the two nodes -- a disconnected graph. I conclude that the only case where we might result in the trivial graph is if we start with a complete graph.

The wikipedia article on connectivity states that "In particular, a complete graph with n vertices, denoted Kn, has no vertex cuts at all, but the vertex-connectivity is n − 1."

So I am left thinking that the original implementation on this function was correct, and the addition of specialized code to handle complete graphs was added (incorrectly) to produce "cuts" which lead to trivial graphs rather than disconnected graphs. That is, the added code made the node_connectivity equal to the size of the node cut-set. That trait is true for all graph except for complete graphs.

OK... enough of this train of thought writing. :}
I think we should remove the code that handles complete graphs specially and fix the tests to check for equality of node_connectivity with the length of the cut sets unless the graph is a complete graph.

Thoughts?

[navyagarwal]

I too read a couple of articles yesterday that discussed cut sets with regard to complete graphs. (refer CMU lecture notes, Wolfram MathWorld).

All sources said that complete graphs have no vertex cut, even though the vertex-connectivity is n − 1.

I think we should remove the code that handles the case of complete graphs. The test cases should check that in case of complete graphs, list(all_node_cuts(KN_graph) should be empty and of size node_connectivity in other cases.

[dschult]

I agree. Make the code return an empty set when the input is a complete graph. I think this just means deleting the special case handling code, but we better check that. :)
And let's change the current tests for complete graphs and change them to check the empty cut return value while also checking that node_connectivity is n-1 in that case.

[navyagarwal]

Make the code return an empty set when the input is a complete graph. I think this just means deleting the special case handling code, but we better check that.

I ran the code after removing the special condition, but it does not give the required output. This is what we get -

graph = nx.Graph()
graph.add_edge(1,2)
list(nx.all_node_cuts(graph))
>>> [{1}]

graph = nx.complete_graph(5)
list(nx.all_node_cuts(graph))
>>> [{0, 1, 2, 3}]

So, I have modified the condition to return an empty generator instead in the PR.

[dschult]

I've finally gotten back to this and found some other problematic cases. I don't trust this functoin at the moment. :}

G=nx.complete_graph(5)
G.remove_edges_from([(0, 1), (3, 4)])
print(list(nx.all_node_cuts(G)))  # returns [{0, 1, 2}]

So it found {0, 1, 2} as a node cut that leaves nodes 3 and 4 (which are disconnected).
But it doesn't find {2, 3, 4} which is also a node cut that leaves nodes 0 and 1 (which are disconnected).

Am I missing something? Have I mixed up something with the definition of node cut?

[navyagarwal]

@dschult You're right, it seems that the problem is not just the edge cases.

I'm also surprised by the fact that when I run the following code (which is the same as above except for the edges removed) the answer comes out to be correct -

G = nx.complete_graph(5)
G.remove_edges_from([(1, 2), (0, 4)])
print(list(nx.all_node_cuts(G))) # returns [{1, 2, 3}, {0, 3, 4}]

I have been trying to understand the issue with this function but haven't come up with anything yet, but I'll keep looking.

[dschult]

Thank you for this bug-report. There was indeed an incorrect handling of complete graphs. And it helped us find a bug in the algorithm more generally.
#6558 fixes those two bug.