Matroid Theory: Graphic & Linear Matroids and When the Greedy Algorithm Is Guaranteed Optimal

1. The Three Matroid Axioms & The Rado-Edmonds Theorem

A subset system $M = (E, \mathcal{I})$, where $E$ is a finite ground set and $\mathcal{I} \subseteq 2^E$ is a family of independent sets, is called a Matroid (Whitney, 1935) if it satisfies three axioms:

1. Non-Emptiness: $\emptyset \in \mathcal{I}$.
2. Hereditary Property (Downward Closure): If $B \in \mathcal{I}$ and $A \subseteq B$, then $A \in \mathcal{I}$.
3. Exchange Property (Augmentation): If $A, B \in \mathcal{I}$ and $|A| < |B|$, then there exists some element $x \in B \setminus A$ such that $A \cup \{x\} \in \mathcal{I}$. (Consequently, all maximal independent sets—called bases—have the exact same cardinality $\text{rank}(E)$!)

2. Canonical Matroids in Systems & Competitive Programming

• Graphic Matroid $M(G)$ (Kruskal's MST): $E$ is the edge set of an undirected graph $G$, and $I \in \mathcal{I}$ iff $I$ is a forest (contains no cycles). Independence testing $S \cup \{e\} \in \mathcal{I}$ takes $O(\alpha(V))$ time using Disjoint Set Union (DSU).
• Linear / Vector Matroid over $\mathbb{F}_2$ (XOR Basis): $E$ is a set of $d$-bit integers (vectors in $\mathbb{F}_2^d$), and $I \in \mathcal{I}$ iff the vectors in $I$ are linearly independent under bitwise XOR ($\oplus$). Maintaining an upper-triangular XOR Basis of size $\le d$ tests independence and inserts a new $64$-bit vector in $O(d)$ bitwise operations!
• Transversal / Unit-Time Deadline Scheduling Matroid: Jobs with unit processing time $t_i = 1$, deadlines $d_i \in \{1..n\}$, and profits $w_i > 0$. A subset of jobs $S$ is independent iff they can all be scheduled before their deadlines (checked in $O(\alpha(n))$ time by DSU: assign each job to the latest free slot $\le d_i$).
• Why Bipartite Matching Is NOT a Matroid: In a 4-vertex path $u_1 - v_1 - u_2 - v_2$, $A = \{(v_1, u_2)\}$ (size 1) and $B = \{(u_1, v_1), (u_2, v_2)\}$ (size 2) are both valid matchings, yet neither edge in $B$ can be added to $A$ without sharing a vertex! Instead, Bipartite Matching is the intersection of two Partition Matroids ($M_1$ restricts left-degrees $\le 1$, $M_2$ restricts right-degrees $\le 1$). Optimizing over the intersection of 2 matroids is solvable in polynomial time (Augmenting Paths / Matroid Intersection), whereas the intersection of $\ge 3$ matroids is NP-hard!

3. Complexity Matrix

4. Reference C++20 Implementation

#include <algorithm>
#include <array>
#include <cstdint>
#include <numeric>
#include <vector>

// 1. Linear Matroid over GF(2): Maximum Weight Linearly Independent XOR Basis
struct WeightedVector {
    std::uint64_t mask;
    long long weight;
};

long long max_weight_xor_basis(std::vector<WeightedVector> elements) {
    // Rado-Edmonds Greedy: sort descending by weight
    std::sort(elements.begin(), elements.end(), [](const WeightedVector& a, const WeightedVector& b) {
        return a.weight > b.weight;
    });

    std::array<std::uint64_t, 64> basis{};
    long long total_weight = 0;

    auto try_insert = [&](std::uint64_t x) -> bool {
        for (int b = 63; b >= 0; --b) {
            if (!((x >> b) & 1ULL)) continue;
            if (basis[b] == 0) {
                basis[b] = x;
                return true; // x is linearly independent of current basis!
            }
            x ^= basis[b];
        }
        return false; // x reduced to 0 -> linearly dependent
    };

    for (const auto& elem : elements) {
        if (elem.weight <= 0) break;
        if (try_insert(elem.mask)) {
            total_weight += elem.weight;
        }
    }
    return total_weight;
}

// 2. Unit-Time Deadline Scheduling Matroid with DSU Slot Allocation
struct DeadlineJob {
    int deadline; // 1-indexed deadline in [1..n]
    long long profit;
};

long long max_profit_deadline_scheduling(std::vector<DeadlineJob> jobs, int max_deadline) {
    std::sort(jobs.begin(), jobs.end(), [](const DeadlineJob& a, const DeadlineJob& b) {
        return a.profit > b.profit;
    });

    // parent[t] points to the latest available time slot <= t (0 means no slot free)
    std::vector<int> parent(max_deadline + 1);
    std::iota(parent.begin(), parent.end(), 0);

    auto find_free_slot = [&](auto& self, int t) -> int {
        return parent[t] == t ? t : (parent[t] = self(self, parent[t]));
    };

    long long total_profit = 0;
    for (const auto& job : jobs) {
        if (job.profit <= 0) break;
        int d = std::min(job.deadline, max_deadline);
        int free_slot = find_free_slot(find_free_slot, d);
        if (free_slot > 0) {
            total_profit += job.profit;
            // Occupy free_slot by merging it into free_slot - 1
            parent[free_slot] = find_free_slot(find_free_slot, free_slot - 1);
        }
    }
    return total_profit;
}