Matroid Intersection
(matroid/matroid_intersection.hpp)
- View this file on GitHub
- Last update: 2026-07-01 14:07:14+09:00
- Include:
#include "matroid/matroid_intersection.hpp"
Overview
matroid_intersection finds a largest subset that is independent in two
matroids on the same ground set. It implements the unweighted augmenting-path
algorithm on the matroid exchange graph.
The ground set is {0, 1, ..., ground_size - 1}. You provide one independence
oracle for each matroid:
bool oracle(const std::vector<int>& subset);
An oracle returns whether subset is independent in its matroid. The order of
the elements is unspecified and must not affect the answer. The vector contains
no duplicates and is only valid during the call.
UniformMatroid, PartitionMatroid, GraphicMatroid, LinearMatroid, and
BinaryLinearMatroid already provide this interface and can be passed
directly. Custom callables are supported as well.
This header solves the maximum-cardinality, unweighted problem. It does not solve weighted matroid intersection.
Interface
template <class IndependenceOracle1, class IndependenceOracle2>
std::vector<int> matroid_intersection(
int ground_size,
IndependenceOracle1 oracle1,
IndependenceOracle2 oracle2);
The returned vector contains the elements of one maximum common independent set in increasing order. Both oracles are copied into the function and may keep mutable scratch storage internally, but they must consistently describe fixed matroids throughout the call.
The canonical namespace and include are:
#include "matroid/matroid_intersection.hpp"
m1une::matroid::matroid_intersection(...);
How the Algorithm Uses the Oracles
Let $S$ be the current common independent set.
- An outside element $x$ is a source when $S+x$ is independent in the first matroid.
- It is a sink when $S+x$ is independent in the second matroid.
- The exchange graph contains $y\to x$ when $S-y+x$ is independent in the first matroid.
- It contains $x\to y$ when $S-y+x$ is independent in the second matroid.
-
A shortest source-to-sink path is toggled to increase $ S $ by one.
If no such path exists, $S$ has maximum cardinality.
Complexity
Let $N$ be ground_size, $R$ be the size of the returned set, and $C_1,C_2$
be the costs of the two oracle calls. The implementation uses
time in the worst case and $O(N)$ additional memory. Each oracle receives at most $R+1$ elements; include the cost of scanning that vector in $C_i$.
This generic version is intended for small or medium explicit ground sets. A problem-specific matching, flow, or linear-algebra algorithm is usually faster when one exists.
Example: Two Partition Matroids
Suppose every item has a color and a shape, and at most one item of each color and each shape may be selected.
#include "matroid/matroid_intersection.hpp"
#include "matroid/partition_matroid.hpp"
#include <iostream>
#include <vector>
int main() {
std::vector<int> color = {0, 0, 1, 1};
std::vector<int> shape = {0, 1, 0, 2};
m1une::matroid::PartitionMatroid by_color(color);
m1une::matroid::PartitionMatroid by_shape(shape);
auto selected = m1une::matroid::matroid_intersection(
int(color.size()), by_color, by_shape);
std::cout << selected.size() << "\n"; // 3
}
Required by
Verified with
Code
#ifndef M1UNE_MATROID_MATROID_INTERSECTION_HPP
#define M1UNE_MATROID_MATROID_INTERSECTION_HPP 1
#include <algorithm>
#include <cassert>
#include <vector>
namespace m1une {
namespace matroid {
template <class IndependenceOracle1, class IndependenceOracle2>
std::vector<int> matroid_intersection(int ground_size, IndependenceOracle1 oracle1,
IndependenceOracle2 oracle2) {
assert(0 <= ground_size);
std::vector<char> selected(ground_size, false);
std::vector<int> elements;
std::vector<int> position(ground_size, -1);
while (true) {
std::vector<char> source(ground_size, false);
std::vector<char> sink(ground_size, false);
std::vector<int> distance(ground_size, -1);
std::vector<int> previous(ground_size, -1);
std::vector<int> queue;
queue.reserve(ground_size);
for (int x = 0; x < ground_size; x++) {
if (selected[x]) continue;
elements.push_back(x);
source[x] = oracle1(elements);
sink[x] = oracle2(elements);
elements.pop_back();
if (source[x]) {
distance[x] = 0;
queue.push_back(x);
}
}
int target = -1;
for (int head = 0; head < int(queue.size()) && target == -1; head++) {
int v = queue[head];
if (!selected[v] && sink[v]) {
target = v;
break;
}
if (selected[v]) {
int index = position[v];
assert(index != -1 && elements[index] == v);
for (int x = 0; x < ground_size; x++) {
if (selected[x] || distance[x] != -1) continue;
elements[index] = x;
bool independent = oracle1(elements);
elements[index] = v;
if (!independent) continue;
distance[x] = distance[v] + 1;
previous[x] = v;
queue.push_back(x);
}
} else {
for (int y : elements) {
if (distance[y] != -1) continue;
int index = position[y];
assert(index != -1 && elements[index] == y);
elements[index] = v;
bool independent = oracle2(elements);
elements[index] = y;
if (!independent) continue;
distance[y] = distance[v] + 1;
previous[y] = v;
queue.push_back(y);
}
}
}
if (target == -1) break;
for (int v = target; v != -1; v = previous[v]) selected[v] = !selected[v];
elements.clear();
std::fill(position.begin(), position.end(), -1);
for (int x = 0; x < ground_size; x++) {
if (!selected[x]) continue;
position[x] = int(elements.size());
elements.push_back(x);
}
#ifndef NDEBUG
assert(oracle1(elements));
assert(oracle2(elements));
#endif
}
return elements;
}
} // namespace matroid
} // namespace m1une
#endif // M1UNE_MATROID_MATROID_INTERSECTION_HPP#line 1 "matroid/matroid_intersection.hpp"
#include <algorithm>
#include <cassert>
#include <vector>
namespace m1une {
namespace matroid {
template <class IndependenceOracle1, class IndependenceOracle2>
std::vector<int> matroid_intersection(int ground_size, IndependenceOracle1 oracle1,
IndependenceOracle2 oracle2) {
assert(0 <= ground_size);
std::vector<char> selected(ground_size, false);
std::vector<int> elements;
std::vector<int> position(ground_size, -1);
while (true) {
std::vector<char> source(ground_size, false);
std::vector<char> sink(ground_size, false);
std::vector<int> distance(ground_size, -1);
std::vector<int> previous(ground_size, -1);
std::vector<int> queue;
queue.reserve(ground_size);
for (int x = 0; x < ground_size; x++) {
if (selected[x]) continue;
elements.push_back(x);
source[x] = oracle1(elements);
sink[x] = oracle2(elements);
elements.pop_back();
if (source[x]) {
distance[x] = 0;
queue.push_back(x);
}
}
int target = -1;
for (int head = 0; head < int(queue.size()) && target == -1; head++) {
int v = queue[head];
if (!selected[v] && sink[v]) {
target = v;
break;
}
if (selected[v]) {
int index = position[v];
assert(index != -1 && elements[index] == v);
for (int x = 0; x < ground_size; x++) {
if (selected[x] || distance[x] != -1) continue;
elements[index] = x;
bool independent = oracle1(elements);
elements[index] = v;
if (!independent) continue;
distance[x] = distance[v] + 1;
previous[x] = v;
queue.push_back(x);
}
} else {
for (int y : elements) {
if (distance[y] != -1) continue;
int index = position[y];
assert(index != -1 && elements[index] == y);
elements[index] = v;
bool independent = oracle2(elements);
elements[index] = y;
if (!independent) continue;
distance[y] = distance[v] + 1;
previous[y] = v;
queue.push_back(y);
}
}
}
if (target == -1) break;
for (int v = target; v != -1; v = previous[v]) selected[v] = !selected[v];
elements.clear();
std::fill(position.begin(), position.end(), -1);
for (int x = 0; x < ground_size; x++) {
if (!selected[x]) continue;
position[x] = int(elements.size());
elements.push_back(x);
}
#ifndef NDEBUG
assert(oracle1(elements));
assert(oracle2(elements));
#endif
}
return elements;
}
} // namespace matroid
} // namespace m1une