CS Paper Radar

Subquadratic-Query Algorithms for Finding Another Maximum Matroid Intersection

Makoto Watanabe

cs.DS ·submitted 2026-09-16 06:34 UTC · v1

Abstract

Let $\mathcal{M}_1,\mathcal{M}_2$ be two matroids on a common ground set $V$, given by independence oracles, and let $S$ be a maximum-cardinality common independent set. We study the problem of deciding whether there exists another maximum common independent set $T\ne S$, and of outputting one when it exists. Writing $n=|V|$ and $r=|S|$, we give a Las Vegas algorithm using $\tilde O(n\sqrt r)$ expected independence queries and a deterministic algorithm using $\tilde O(nr^{2/3})$ queries. As an application, all maximum common independent sets can be enumerated with at most two another-solution calls between consecutive outputs and after the last output; if there are $L$ solutions, exactly $2L-1$ such calls are made. Neither algorithm constructs the exchange graph. Instead, they perform Kahn-style source peeling through two deletion-only data structures. One side uses the heavy/light categorization of Blikstad, van den Brand, Mukhopadhyay, and Nanongkai. For the opposite side, where no transposed oracle is available, we give a collective randomized classifier and a deterministic capacity-saturation certificate.

Closest papers

Nearest neighbours by meaning across the whole index.

A Faster Auction Algorithm for Weighted Matroid Intersection

cs.DS ·2026-10-01 ·Tatsuya Terao
similarity 0.78
Abstract · 17 pages. In this version, we have completely rewritten the proof, which is now simpler and easier to follow, and improved the clarity and p…

We consider the weighted matroid intersection problem in the independence-oracle model. A sequence of works by Huang--Kakimura--Kamiyama~[SODA'16 \& Math. Program'19], Chekuri--Quanrud~[SODA'16], Quanrud~[ICALP'24], and Dudeja--Grilnberger~[IPCO'26] has developed efficient $(1-\varepsilon)$-approximation algorithms for this problem. We present a simple deterministic auction algorithm that, given two matroids on a common ground set of size $n$, computes a $(1-\varepsilon)$-approximate maximum-weight common independent set using $O(n \varepsilon^{-2} \log^2(n))$ independence-oracle queries. This is the first deterministic $(1-\varepsilon)$-approximation algorithm for the weighted matroid intersection problem whose query complexity is nearly linear in $n$ and polynomial in $1/\varepsilon$. Our algorithm builds on the auction algorithm for unweighted matroid intersection by Huang--Kobayashi~['26].

0.28

A Faster Scaling Algorithm for Maximum Weight Matroid Intersection

cs.DS ·2026-11-11 ·Alina Ene, Huy L. Nguyen
similarity 0.74
Abstract

We consider the maximum weight matroid intersection problem. In this problem, we are given two matroids $M_{1}=(E,\mathcal{I}_{1})$ and $M_{2}=(E,\mathcal{I}_{2})$ and integer weights $w(e)$ on the elements $e\in E$, and the goal is to find a maximum-weight common independent set. We give a randomized algorithm that constructs an optimal solution using $\widetilde{O}(nr\log W)$ queries to the independence oracles of the matroids, where $n$ is the size of the ground set $E$, $r$ is the minimum rank of the two matroids, and $W$ is the maximum weight.

0.07

Graphic Matroid Secretary without the Graph

cs.DS ·2026-08-11 ·Paul Dütting, Renato Paes Leme, Martin Pál, Neel Patel
similarity 0.71
Abstract

The matroid secretary problem (MSP) is one of the cleanest, and most captivating open problems in online algorithms. The famous MSP conjecture stipulates that there exists a constant-competitive algorithm, yet to date the best known algorithms are $O(\log \log (\text{rank}))$ competitive. It is widely believed that all information that an algorithm for the MSP should use is information that is available through an independence oracle on the already arrived elements. Despite this, there are natural classes of matroids where a constant-competitive algorithm is known if we are given additional upfront information about the matroid; while no such algorithm is known if all the algorithm can use is an independence oracle on the arrived elements. In this work, we tackle the perhaps most appealing such class of matroids, graphic matroids. We develop an algorithm for the MSP that has access to the independence oracle only. Our algorithm runs in polynomial time, and if the underlying matroid is graphic, it produces an independent set whose weight is at least $1/36$ of the maximum-weight independent set. Ours is the first constant-competitive algorithm for MSP on unknown graphic matroids.

0.42

As Easy as Rank One: Optimal Algorithms for Matroid Secretary and Single-Sample Matroid Prophet

cs.DS cs.GT ·2026-11-06 ·Hamed Abdi, Kiarash Banihashem, MohammadTaghi Hajiaghayi, Zhiyi Huang, Danny Mittal +1 more
similarity 0.70
Abstract · This paper merges and extends arXiv:2609.14555, arXiv:2609.19118, and arXiv:2609.30421

We resolve the matroid secretary conjecture in its strong form and the single-sample matroid prophet inequality problem, achieving competitive ratios $e$ and $2$, respectively. Both ratios are optimal, even for rank-one matroids. For matroid secretary, our ordinal algorithm accepts the elements of the canonical optimum independently, each with probability $1/e$. It needs only the number of elements in advance and uses an expected polynomial number of independence queries on arrived elements. For single-sample matroid prophet inequalities, our algorithm uses one sample per independent value distribution and $O(n^2)$ independence queries on a known $n$-element matroid. It works for every arrival order fixed independently of the samples, values, and algorithmic randomness. The selected elements and their values have exactly the joint distribution obtained by independently retaining each element--value pair in the canonical optimum of a fresh product draw with probability $1/2$. Our main algorithms maintain a reference state whose greedy solution contains every accepted element. Its updates, made even after rejections, preserve exact distributional invariants. A short reversible-update argument gives a $4$-probability-competitive secretary algorithm, already resolving the original conjecture; a related invariant gives the optimal single-sample prophet inequality. For secretary, we characterize the distributions achievable by ordinal algorithms through a finite polytope. A continuous-time formulation then lets us design an accepted-set distribution achieving the optimal ratio $e$ and realize it efficiently. We also obtain guarantees for matroid intersections.

0.39

Matroid Connectedness and Component Decomposition: Breaking the Quadratic Barrier

cs.DM ·2026-11-17 ·Manuel Aprile, Roberto Ronco
theory similarity 0.70
Abstract

Deciding whether a matroid is connected and computing its connected components are two fundamental algorithmic problems in matroid theory. Since the 1970s, the best known algorithms for both problems have used $O(n^2)$ independence queries on an $n$-element ground set. Our main contribution is to break this quadratic barrier: we give a deterministic algorithm that computes all connected components of a matroid on $n$ elements with $O(n \log{n})$ independence queries. Our algorithm for component decomposition combines fundamental basis exchanges with a disjoint-set union data structure, avoiding the explicit construction of the fundamental graph. Moreover, we show that our algorithm is asymptotically optimal by giving a lower bound based on a simple information-theoretic argument: any (deterministic or bounded-error randomized) algorithm to compute connected components needs $Ω(n \log{n})$ independence queries. Then, we turn to the query complexity of deciding whether a matroid is connected. For this problem, we present an algorithm that uses $O(nh)$ independence queries, where $h \ge 1$ bounds the size of any chain of nonempty proper cyclic flats. The algorithm achieves asymptotically optimal linear query complexity on elementary split matroids, that include all paving matroids, and on arbitrary direct sums of uniform matroids.

0.15

From Linear to Polylogarithmic: Dynamic Submodular Maximization over Matroids

cs.DS ·2026-10-26 ·Kiarash Banihashem, Samira Goudarzi, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Morteza Monemizadeh
similarity 0.69
Abstract

We study the problem of submodular maximization under a matroid constraint. In this problem, there is a monotone submodular function $f: 2^{N} \rightarrow \mathbb{R}^+$ and a matroid $M(N, I)$, accessible via value and independence oracles and the goal is to find the independent set $S \in I$ maximizing the objective function, i.e., $f(S) = \max_{I \in I} f(I)$. In the fully dynamic setting, the active ground set $N \subseteq N$ evolves through element insertions and deletions. The goal is to maintain a solution $S \subseteq N$ with $S \in I$ and $f(S) = \max_{I \subseteq N,, I \in I} f(I)$ after each update. Two approximation algorithms have been proposed to solve this problem: Dütting et al. developed a $(4+ε)$-approximation algorithm with an expected amortized update time of $O\!\bigl(\frac{k^2}ε \log k \log n \log^3 \frac{k}ε\bigr)$, and Banihashem et al. achieved a similar approximation with a better update time $O\!\bigl(k \log k \log^3 \frac{k}ε\bigr)$. However, these methods both become inefficient when the rank $k$ of the matroid is large (e.g., when $k = n^{o(1)}$). The central open question in this line of work is whether a fully dynamic algorithm with polylogarithmic update time exists. We resolve this question by presenting the first fully dynamic algorithm for submodular maximization over matroids with polylogarithmic update time. Our algorithm maintains a $(4+ε)$-approximate solution with expected amortized update time $poly(\log n, ε^{-1})$, where $n = |N|$. In particular, the update time is independent of the matroid rank $k$, thereby eliminating the dependence on $k$ and settling the open problem.

0.29

Weighted Matroid Intersection under Minimum Rank Oracle

cs.DM math.COmath.OC ·2026-11-07 ·Taihei Oki
theory similarity 0.69
Abstract

We consider matroid intersection under the minimum rank oracle model, in which two matroids are accessible only through an oracle that returns the minimum of the ranks of a given set in the two matroids. By Edmonds' theorem, this oracle determines the matroid intersection polytope, although it does not reveal the exchangeability graphs on which classical algorithms rely. Recent work by Bárász, Bérczi, Király, Oki, Yamaguchi, and Yokoi (2025) showed that unweighted matroid intersection is polynomially solvable in this model. In this paper, we present a strongly polynomial-time algorithm for weighted matroid intersection in this model. The key to our algorithm is a polynomial-size extended formulation of tangent cones of common base polytopes that can be constructed using the minimum rank oracle. We also give min-max theorems in terms of the minimum rank function via 1/3-submodularity, and present a strongly polynomial-time algorithm to compute an optimal dual solution.

0.14

Analysis of the two-for-one swap heuristic for approximating the maximum independent set in a k-polymatroid

cs.DS ·2026-10-06 ·Adrian Calinescu, Gruia Calinescu
published similarity 0.66
Abstract

Let f:2^N --> \cZ^+ be a polymatroid (an integer-valued non-decreasing submodular set function with f(emptyset) = 0). A k-polymatroid satisfies that f(e) <= k for all e in N. We call a subset S of N independent if f(S) equals the sum of f(e) over the elements e of S and f(e) > 0 for all e in S. Finding a maximum-size independent set in a 2-polymatroid has been studied and polynomial-time algorithms are known for linear polymatroids. For k >= 3, the problem is NP-hard, and an approximation algorithm with ratio approaching 2/k is known and is obtained by swapping as long as possible a "large" subset from the current solution by a set with one more element. Here we give a simple analysis of the more particular two-for-one repeated swapping heuristic, obtaining a (weaker) 2/(k+1)-approximation.

0.24