Graph Mining – 1 | 09. Highly Connected Subgraphs and Minimum Cuts — Part 3 (Q&A)

AI Generated Answers. Original questions are attributed to Sayed Ahmed and appeared on this blog. The newly AI-generated instructional answers, code and original examples are provided for reuse without copyright restrictions asserted by the site. External materials keep their own terms. Check algorithms and assumptions.

Graph Mining – 1 course index · Original questions: Highly Connected Subgraph Clustering · Covers 09.41–09.58.

Scope: The classical HCS condition λ(H)>|V_H|/2 refers to simple unweighted undirected graphs. Weighted capacities and directed graphs require adapted definitions.

Q09.41. What is the core concept of Karger’s algorithm?

Answer. Repeatedly contract randomly selected edges, preserving the cut capacity of surviving edges. When two supervertices remain, the edges between them define a candidate cut. Random choices can destroy an optimal cut, hence the need for repetitions.

Q09.42. What is the “contraction of an edge” in Karger’s algorithm?

Answer. Contracting (u,v) merges u and v into one supervertex representing their combined original vertices. Reattach external edges to the supervertex, preserve parallel edges, and delete self-loops formed by internal connections.

Q09.43. What is the number of edge reduction caused by “contraction of an edge”?

Answer. Each successful contraction reduces the number of supervertices by exactly 1. The reduction in the number of edges is variable: all self-loops created by the merge disappear, while parallel external edges remain.

Q09.44. In Karger’s algorithm when you merge two nodes u and v, what happens to the edges that were previously connected to those nodes?

Answer. Edges to outside vertices are redirected to the merged supervertex. If both u and v were adjacent to some w, parallel edges may now connect the supervertex to w; they must retain multiplicity or equivalent summed capacity. Internal edges become self-loops and are discarded.

Q09.45. What is the complexity of Karger’s algorithm?

Answer. Runtime depends on data structures. A textbook implementation can be arranged to take roughly O(n²) time for one contraction trial; a straightforward implementation that rescans all E edges after every one of n contractions can take O(nE). Repeating trials multiplies that cost.

Q09.46. What is the complexity of Karger’s algorithm? is it O(E) or O(V) or O (Log(E))

Answer. None of O(E), O(V), or O(log E) is a generally correct universal bound for the whole simple algorithm. It makes n−2 contractions and must maintain cut-edge multiplicities. State the implementation: O(n²) is a standard per-trial bound for an efficient implementation; naïve repeated edge scans can be O(nE).

Q09.47. Describe Karger’s algorithm?

Answer. Karger’s randomized minimum-cut algorithm treats a connected undirected graph as a multigraph, picks a random edge uniformly from the current edges, contracts it, deletes resulting self-loops, and repeats until two supervertices remain. The remaining parallel-edge count is the trial’s cut value.

Q09.48. Give the steps in Karger’s algorithm?

Answer. Steps: (1) copy G; (2) while more than two supervertices remain, choose a random current edge; (3) merge endpoints; (4) delete self-loops, retaining parallel edges; (5) return the cut between the two final groups; (6) repeat independent trials to improve confidence.

Q09.49. Describe Pseudo-code and Python/C++/R/Java code for Karger’s algorithm?

Answer. See the full Python implementation below. It keeps original edges as a multiset, maintains vertex-to-supervertex membership, randomly chooses a surviving crossing edge, and returns the partition/cut size. Preserve parallel edges; collapsing them into one edge would bias the procedure.

Q09.50. What is the input for Karger’s algorithm? What is the output?

Answer. Input: a connected undirected graph or multigraph with at least two vertices, optionally positive capacities. Output from one trial: a partition of original vertices into two nonempty sets and its cut size/capacity. It is only a candidate global minimum.

Q09.51. What is the terminating condition for Karger’s algorithm?

Answer. Stop contracting when exactly two supervertices remain. The count of edges between them defines the cut for that trial.

Q09.52. Can you continue with Karger’s algorithm when there are <= 2 vertices left?

Answer. Not under the usual algorithm. With two supervertices, the cut is ready. Contracting again would leave one vertex and erase the partition that defines the candidate cut.

Q09.53. Give the minimum cut for the following Graph using Karger’s algorithm? STEPS: while there are more than 2 vertices, pick a random edge (u, v), contract u and v into one vertex, reattach the edges of u and v to this new vertex, remove self-loops. Keep doing. Graph, Edges: {0, 1} {0, 2} {0, 3} {1, 3} {2, 3} Also, show all the steps in picture or text

Answer. For the original four-vertex graph with edges (0,1),(0,2),(0,3),(1,3),(2,3), one successful run contracts (0,3) into A={0,3}, leaving two parallel edges to 1 and two to 2; then contracts (A,1), leaving groups {0,1,3} and {2} with two crossing edges. Therefore the minimum cut is 2. A different random contraction order could return cut 3 instead.

Q09.54. Will Karger’s algorithm? always create Min Cut?

Answer. No. One run may contract an edge belonging to the true minimum cut, eliminating that optimal partition. Karger returns a candidate; repeating independent trials increases the chance of finding a global optimum.

Q09.55. What is the probability that Karger’s algorithm will create Min Cut?

Answer. For any fixed minimum cut of an undirected n-vertex connected graph, one standard contraction trial preserves it with probability at least 2/[n(n−1)]. The actual success chance may be higher when several different global minimum cuts exist.

Q09.56. For a 10 node graph, is the probability = 1/100?

Answer. No. The universal lower bound at n=10 is 2/(10×9)=1/45≈2.22%, not exactly 1/100. It is a lower bound for a fixed minimum cut, not the exact success probability of every 10-node graph.

Q09.57. If Karger’s algorithm is not supposed to generate the min-cut always, how can you increase the probability of creating i.e. implement in such a way so that you increase your chances to find the min-cut before applying for Highly Connected Subgraph Clustering algorithm?

Answer. Run independent trials with different random choices; keep the smallest observed cut. If one trial succeeds with probability at least q, then r independent trials succeed at least once with probability ≥1−(1−q)^r. For guaranteed exact results on moderate graphs, prefer Stoer–Wagner.

Q09.58. Can running the Karger’s algorithm multiple/sufficient times and then taking the least cut found so far will produce better min-cut and better highly connected clusters (than just running once)?

Answer. Yes. Taking the smallest cut seen over repeated independent trials cannot be worse than taking the first result. It raises the chance of identifying the true minimum cut, which generally makes downstream HCS splits more reliable; it does not guarantee perfect clusters or solve all modeling errors.

From-scratch Karger contraction (unweighted)

import random

def karger_trial(vertices, edges, seed=None):
    rng = random.Random(seed)
    # Keep original edge copies: multiplicity matters.
    groups = {v: {v} for v in vertices}
    owner = {v: v for v in vertices}
    while len(groups) > 2:
        crossing = [(u,v) for (u,v) in edges if owner[u]!=owner[v]]
        if not crossing:
            raise ValueError("Input graph was disconnected")
        u,v = rng.choice(crossing)
        a,b = owner[u],owner[v]
        # merge b into a
        for x in groups[b]: owner[x] = a
        groups[a] |= groups.pop(b)
    cut = sum(owner[u]!=owner[v] for u,v in edges)
    return cut, list(groups.values())

V = [0,1,2,3]
E = [(0,1),(0,2),(0,3),(1,3),(2,3)]
trials = [karger_trial(V,E,seed=i) for i in range(100)]
cut, partition = min(trials, key=lambda x: x[0])
print("minimum found:", cut, "groups:", partition)
assert cut == 2
# Try one trial: it may return 2 or 3.
# For an exact check:
import networkx as nx
G=nx.Graph();G.add_nodes_from(V);G.add_edges_from(E)
assert nx.stoer_wagner(G)[0] == cut

Practical caution: The example retries 100 fixed random seeds only to illustrate probability amplification. On real graphs choose a documented confidence target or use exact min-cut. The simple code rescans the edge list after each contraction, so it is not the optimized O(n²) implementation described in theory.

Further reading

HCS clustering algorithm overview · NetworkX edge connectivity · NetworkX Stoer–Wagner. These are linked references, not content copied into this original answer bank.

Leave a Reply