bipartite

Bipartite graph analysis and matching algorithms.

A graph is bipartite (2-colorable) if its vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. Equivalently, a bipartite graph contains no odd-length cycles.

Algorithms

Problem	Algorithm	Function	Complexity
Bipartite check	BFS 2-coloring	`is_bipartite/1`, `partition/1`	O(V + E)
Maximum matching	Augmenting paths	`maximum_matching/1`	O(VE)
Stable matching	Gale-Shapley	`stable_matching/2`	O(V²)

Key Concepts

Bipartite Graph: Vertices partitioned into two sets L and R, edges only go between sets
2-Coloring: Adjacent vertices always have different colors (equivalent to bipartite)
Matching: Set of edges without common vertices
Maximum Matching: Matching with largest possible number of edges
Perfect Matching: Every vertex is matched (requires |L| = |R|)
Stable Matching: No unmatched pair prefers each other over current matches

Characterizations of Bipartite Graphs

A graph is bipartite if and only if:

It is 2-colorable
It contains no odd-length cycles
Its spectrum is symmetric about 0

König’s Theorem

In bipartite graphs, the size of the maximum matching equals the size of the minimum vertex cover. This is a fundamental result that doesn’t hold for general graphs.

Use Cases

Job assignment: Workers to tasks they can perform
Scheduling: Time slots to events without conflicts
Recommendation systems: Users to items they might like
Chemistry: Matching molecules for reactions
Stable marriage: Matching medical residents to hospitals

References

Types

Partition

</>

Represents a partition of a bipartite graph into two independent sets. In a bipartite graph, all edges connect vertices from left to right, with no edges within left or within right.

pub type Partition {
  Partition(left: set.Set(Int), right: set.Set(Int))
}

Constructors

Partition(left: set.Set(Int), right: set.Set(Int))

StableMarriage

</>

Result of the stable marriage algorithm.

Contains the matched pairs and allows querying the partner of any person.

pub type StableMarriage {
  StableMarriage(matches: dict.Dict(Int, Int))
}

Constructors

StableMarriage(matches: dict.Dict(Int, Int))

Values

get_partner

</>

pub fn get_partner(
  marriage: StableMarriage,
  person: Int,
) -> option.Option(Int)

Get the partner of a person in a stable matching.

Returns Some(partner) if the person is matched, None otherwise.

is_bipartite

</>

pub fn is_bipartite(graph: model.Graph(n, e)) -> Bool

Checks if a graph is bipartite (2-colorable).

Example

let graph =
  yog.undirected()
  |> yog.add_node(1, Nil)
  |> yog.add_node(2, Nil)
  |> yog.add_node(3, Nil)
  |> yog.add_node(4, Nil)
  |> yog.add_edge(from: 1, to: 2, with: 1)
  |> yog.add_edge(from: 2, to: 3, with: 1)
  |> yog.add_edge(from: 3, to: 4, with: 1)

bipartite.is_bipartite(graph)  // => True (can color as: 1,3 vs 2,4)

Time Complexity: O(V + E)

maximum_matching

</>

pub fn maximum_matching(
  graph: model.Graph(n, e),
  partition: Partition,
) -> List(#(Int, Int))

Finds a maximum matching in a bipartite graph.

A matching is a set of edges with no common vertices. A maximum matching has the largest possible number of edges.

Uses the augmenting path algorithm (also known as the Hungarian algorithm for unweighted bipartite matching).

Returns a list of matched pairs #(left_node, right_node).

Example

let graph =
  yog.undirected()
  |> yog.add_node(1, Nil)  // left
  |> yog.add_node(2, Nil)  // left
  |> yog.add_node(3, Nil)  // right
  |> yog.add_node(4, Nil)  // right
  |> yog.add_edge(from: 1, to: 3, with: 1)
  |> yog.add_edge(from: 1, to: 4, with: 1)
  |> yog.add_edge(from: 2, to: 3, with: 1)

case bipartite.partition(graph) {
  Some(p) -> {
    let matching = bipartite.maximum_matching(graph, p)
    // => [#(1, 3), #(2, 4)] or [#(1, 4), #(2, 3)]
  }
  None -> panic as "Not bipartite"
}

Time Complexity: O(V * E)

partition

</>

pub fn partition(
  graph: model.Graph(n, e),
) -> option.Option(Partition)

Returns the two partitions of a bipartite graph, or None if the graph is not properties.

Uses BFS with 2-coloring to detect bipartiteness and construct the partitions. Handles disconnected graphs by checking all connectivity.

Example

case bipartite.partition(graph) {
  Some(Partition(left, right)) -> {
    // left and right are the two independent sets
    io.println("Graph is bipartite!")
  }
  None -> io.println("Graph is not bipartite")
}

Time Complexity: O(V + E)

stable_marriage

</>

pub fn stable_marriage(
  left_prefs: dict.Dict(Int, List(Int)),
  right_prefs: dict.Dict(Int, List(Int)),
) -> StableMarriage

Finds a stable matching given preference lists for two groups.

Uses the Gale-Shapley algorithm to find a stable matching where no two people would both prefer each other over their current partners.

The algorithm is “proposer-optimal” - it finds the best stable matching for the proposing group (left), and the worst stable matching for the receiving group (right).

Parameters

left_prefs - Dict mapping each left person to their preference list (most preferred first)
right_prefs - Dict mapping each right person to their preference list (most preferred first)

Returns

A StableMarriage containing the matched pairs. Use get_partner() to query matches.

Example

// Medical residency matching
let residents = dict.from_list([
  #(1, [101, 102, 103]),  // Resident 1 prefers hospitals 101, 102, 103
  #(2, [102, 101, 103]),
  #(3, [101, 103, 102]),
])

let hospitals = dict.from_list([
  #(101, [1, 2, 3]),      // Hospital 101 prefers residents 1, 2, 3
  #(102, [2, 1, 3]),
  #(103, [1, 2, 3]),
])

let matching = bipartite.stable_marriage(residents, hospitals)
case get_partner(matching, 1) {
  Some(hospital) -> io.println("Resident 1 matched to hospital " <> int.to_string(hospital))
  None -> io.println("Resident 1 unmatched")
}

Time Complexity: O(n²) where n is the size of each group