Ask Your Question
0

Calculate the toughness of a graph

asked 2024-03-03 14:08:12 +0200

licheng gravatar image

updated 2024-03-04 06:27:29 +0200

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 flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
1

answered 2024-03-03 16:34:58 +0200

Max Alekseyev gravatar image

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)) )
edit flag offensive delete link more

Comments

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.

licheng gravatar imagelicheng ( 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.

David Coudert gravatar imageDavid Coudert ( 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]
        seen.add(u)
        while CC:
            v = CC.pop()
            for w in G.neighbor_iterator(v):
                if w not in seen:
                    CC.append(w)
                    seen.add(w)
    return nb_cc
David Coudert gravatar imageDavid Coudert ( 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.

licheng gravatar imagelicheng ( 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.

David Coudert gravatar imageDavid Coudert ( 2024-03-05 09:15:33 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2024-03-03 14:08:12 +0200

Seen: 138 times

Last updated: Mar 04