# Calculate the toughness of a graph

Let $G$ be a graph. Toughness is defined as $$t(G)=\min _S \frac{|S|}{c(G-S)}$$ where $c$ is the number of connected components and the minimum is taken over all vertex cuts $S$ of $G$ (Graph toughness was first introduced by Václav Chvátal (1973)).

Based on the definition, I have written a code that relies mainly on third-party libraries networkx and itertools. I'm wondering if there is hope to improve its efficiency in the Sage or Python environment.

#Import the networkx library
import networkx as nx
# Import the combinations function from itertools
from itertools import combinations

def is_vertex_cut(G, vertex_cut):
# Create a copy of the graph
H = G.copy()
# Remove the nodes from the given set
H.remove_nodes_from(vertex_cut)
# Check the connectivity of the graph
return not nx.is_connected(H)

def toughness(G):
nodes = G.nodes()
order = G.number_of_nodes() - 2
vertex_conn = nx.node_connectivity(G)
min_toughness = float('inf')  # Initialize the minimum toughness to positive infinity
for r in range(vertex_conn, order):
for j in combinations(nodes, r):
if is_vertex_cut(G, j):
# Create a copy of the graph
H = G.copy()
# Remove the nodes from the given set
H.remove_nodes_from(j)
# Calculate the number of connected components in (G-j)
num_connected_components = nx.number_connected_components(H)
toughness_value = r / num_connected_components
# Update the toughness value
min_toughness = min(min_toughness, toughness_value)

# Return the minimum toughness value
return min_toughness

# Test code
G = nx.cycle_graph(20)

# # G = nx.Graph()
# # G.add_nodes_from([1, 2, 3, 4, 5, 6])
# # G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1)])

min_toughness = toughness(G)
print("toughness:", min_toughness)


Then it gives us the following output:

toughness: 1.0

(run 166.5s)

edit retag close merge delete

Sort by » oldest newest most voted

I'm not sure if the following code is any faster, but it's purely in Sage without using any additional modules:

def remove_cc(G,S):
H = G.copy()
H.delete_vertices(S)
return H.connected_components_number()

def toughness(G):
return min(len(S)/c for S in Subsets(G.vertices()) if (c:=remove_cc(G,S))>=2)

print( toughness(graphs.CycleGraph(20)) )

more

Good! It takes 116s in my computer for the graph CycleGraph(20). When connectivity $k$ is relatively large, excluding subsets smaller than $k$ first theoretically leads to higher efficiency.

( 2024-03-04 06:24:02 +0200 )edit
1

You can use the lowerbounds from https://alco.centre-mersenne.org/item... $t(G) \geq \frac{\mu_n\mu_2}{n(\mu_n - \delta)}$ and $t(G)\geq \frac{\mu_2}{\mu_n - \mu_2}$, where $\delta$ is the minimum degree of the graph and $\mu_i$ is the $i$th smallest eigenvalue of the Laplacian matrix of the graph.

( 2024-03-04 11:04:46 +0200 )edit
1

To count the number of connected components in G-S, the following method avoids a copy of the graph and is faster. I obtain the solution in 16s instead of 50s on my laptop for the graph CycleGraph(20).

def remove_cc(G, S):
r"""
Return the number of connected components in G-S.
"""
seen = set(S)
nb_cc = 0
for u in G:
if u in seen:
continue
# Explore the connected component containing u
nb_cc += 1
CC = [u]
while CC:
v = CC.pop()
for w in G.neighbor_iterator(v):
if w not in seen:
CC.append(w)
return nb_cc

( 2024-03-04 11:23:54 +0200 )edit

Nice! Thank you. I didn't expect to spend so much time in copy a graph. I originally thought iterating through subsets would take a lot of time in this instance, and the time spent on the remaining code steps is negligible, it seems I was mistaken.

( 2024-03-05 03:26:29 +0200 )edit

Improving a method that is called many many times makes a difference. However, it would be better to reduce the number of subsets to consider.

( 2024-03-05 09:15:33 +0200 )edit