Minimum Weight Arborescence | CSCE 500 | Project 5

🧠 Why Are You Learning This?

The minimum-weight arborescence (MWA) problem is a fundamental problem in graph theory with applications in:

• Network design: Finding optimal broadcast trees (e.g., in telecommunication networks).
• Transportation & logistics: Designing efficient supply chain routes.
• Computer science: Used in dependency resolution, spanning tree variants, and approximation algorithms.

It generalizes the minimum spanning tree (MST) problem for directed graphs, where we need a rooted tree that connects all nodes with minimum total weight.

What is Spanning Tree?

A spanning tree is a sub-graph of an undirected connected graph:

1. ✅ Includes all vertices (nodes) of Graph
2. ✅ Has no cycles (i.e., it’s a tree).
3. |V| − 1 edges:
4. This is the minimum number of edges needed to connect all nodes without cycles.

image source

2. Minimum Spanning Tree (MST)

A minimum spanning tree is a spanning tree where the sum of edge weights is the smallest possible.

Key Points:

1. Only exists in weighted graphs (edges have costs).
2. There may be multiple MSTs if some edges have equal weights.

Spanning Tree vs Minimum Spanning Tree

Analogy of Minimum Spanning Tree (MST)

• A network of cities (nodes) connected by roads (edges).
• Each road has a cost (weight) to build.

A minimum spanning tree is a way to connect all cities using the cheapest possible roads, with no loops (you don’t want redundant roads).

Key Properties of MST (Undirected Graphs)

✅ Connects all cities (no isolated cities).

✅ No cycles (no loops in the road network).

✅ Minimum total cost (cheapest way to build roads).

🌳 What is an Arborescence?

A french word which translates to Tree Structure:

Why is this an Arborescence?

1. Directed: All edges (roads) are arrows, showing a one-way connection.
2. Rooted: One node (City at the top) acts as the root, and all other nodes are reachable from it.
3. Tree: There are no cycles, and the graph connects all nodes with exactly one incoming edge (except the root, which has none).

An arborescence is like a spanning tree but with directions:

• Roads are one-way (directed edges).
• You must build roads from a capital city (root) to all others.

✅ One root city (no incoming roads).

✅ Every other city has exactly one incoming road (only one way to reach it).

✅ No cycles (no loops in the road directions).

🔁 Analogy

Imagine you're the president of a student organization (root), and everyone else in the club has exactly one person they report to (in a one-directional, non-looping way). The structure forms a directed tree. that’s an arborescence.

🚀 From Arborescence to Minimum-Weight Arborescence

In real-world scenarios like

1. building roads
2. laying cables
3. setting up networks

cost matters. So instead of any valid arborescence, we want the cheapest one.

The Minimum-Weight Arborescence does just that

It selects edges to form a valid tree structure such that the total sum of the edge weights is minimised.

Properties of Minimum Weight Arborescence:

An arborescence is like a tree in a directed graph. Specifically:

It is a directed version of a tree where:

• It’s a directed tree
• There is one root node .
• All nodes are reachable from the root.
• Every other node has exactly one incoming edge.
• No cycles, and all nodes are reachable from the root.
• Every node is reachable from the root.

Finding the Minimum Weight Arborescence:

So the total minimum weight is 9.

Key Differences from MST

Kruskal's and Prim's algorithms can solve the Minimum Spanning Tree (MST)

What can be used to solve Minimum Weight Arborescence? 

🧮 How Is It Found?

✅ Chu–Liu/Edmonds’ Algorithm

APPROACH: Chu-Liu/Edmonds' Algorithm for Minimum Arborescence

1. INITIALIZATION
 - Start with total weight = 0
 - Root is fixed (vertex 1)

2. MAIN LOOP (repeat until solution found)
 a. SELECT MIN INCOMING EDGES:
  For each vertex (except root),pick its cheapest incoming edge
  These edges form a "reduced graph"

 b. CYCLE DETECTION:
   - Check if the reduced graph contains any directed cycles
   - If NO cycles found:
     * Sum weights of all selected edges → this is our solution
     * Exit algorithm

c. CYCLE CONTRACTION (if cycles exist):
- For each detected cycle:
  * Calculate total weight of cycle edges
  * Contract the cycle into a single supernode
  * Adjust edge weights for edges entering/leaving the cycle:
- For edges ENTERING the cycle: weight = original_weight - selected_incoming_edge_weight
- For edges LEAVING the cycle: weight remains unchanged

d. RECURSION:
- Solve the problem recursively on the contracted graph
- When expanding back:
  * Keep all selected edges except one in each cycle
 * For each cycle,exclude the edge that would create a conflict

3. TERMINATION
 - When graph has no cycles in reduced form
 - Sum of selected edge weights gives the minimal arborescence

Full code is found here:

prashantbasnet94