The paper “Complexity of packing common bases in matroids” by Kristóf Bérczi and Tamás Schwarcz settles an important complexity question about a deceptively simple combinatorial task: can you partition the ground set of two matroids into k disjoint sets that are simultaneously bases of both matroids? As of 2023, their results show this is a much tougher problem than many experts expected, with strong negative results both in the oracle (rank/independence query) model and in concrete NP-hardness settings. Below I unpack what that means, why it matters, and how the authors reach those conclusions.

“One of the most intriguing unsolved questions of matroid optimization is the characterization of the existence of k disjoint common bases of two matroids.”

What does “packing common bases” mean in matroids? (common bases, partitioning ground set into common bases two matroids)

Matroids are an abstraction of the notion of independence that unifies linear algebra (independent columns of a matrix), graph theory (acyclic edge sets), and other combinatorial structures. Each matroid M is defined on a finite ground set E and comes with a family of independent subsets. A base of a matroid is a maximal independent set; in many familiar cases a base corresponds to a spanning tree in a graph or a basis of a vector space.

“Packing common bases” asks this: given two matroids M1 and M2 defined on the same ground set E, can we split E into disjoint pieces B1, B2, …, Bk so that each Bi is a base in both M1 and M2? If yes, we say we have k disjoint common bases. When k *times* the rank equals |E|, this is equivalent to partitioning the entire ground set into k common bases.

So the problem is both structural and algorithmic: find (or decide existence of) a partition of the ground set into common bases of two matroids. This is naturally connected to many classical conjectures and problems in combinatorics and graph theory, because numerous packing and decomposition conjectures can be rephrased as special cases of packing common bases.

Intuition: why partitioning the ground set into common bases two matroids feels tractable but hides complexity

On first glance, matroids often admit elegant greedy algorithms and min-max theorems (e.g., the matroid intersection theorem), so you might expect similar tractability here. Indeed, the matroid intersection problem—finding a maximum-size common independent set of two matroids—has polynomial-time algorithms. But the requirement to partition the entire ground set into multiple common bases is qualitatively different: it’s a global covering/packing constraint, not a single-maximum intersection. That extra combinatorial structure can encode hard logical constraints.

Why is deciding k disjoint common bases hard under the rank/oracle model? (complexity of packing common bases in matroids)

First we must be clear about the computational model. In the rank/oracle (or independence oracle) model, the algorithm does not get an explicit description of the matroid(s) like a matrix or graph. Instead, it can query an oracle that answers “is this set independent?” or “what is the rank of this set?” Each query returns a yes/no or a number, and the algorithm’s complexity is counted in the number of such queries.

Bérczi and Schwarcz prove that even in this abstract model, there is no algorithm that can decide whether the ground set of two matroids can be partitioned into k common bases using only a polynomial number of independence/rank queries. In plain language: using only the standard matroid oracle and polynomially many queries you cannot always decide the packing-of-common-bases question.

Why does this matter? Independence-oracle hardness is a strong impossibility claim: it means there is no ‘black-box’ matroid algorithm that inspects the matroid only by asking membership/rank questions and can always solve the problem efficiently. The proof goes by constructing matroid pairs that are indistinguishable under any polynomial number of queries but differ on whether they admit the desired packing. This is a well-known style of argument in matroid complexity (and shows the problem is information-theoretically hard under that model).

Is the packing common bases problem NP-complete for k=2 or special matroid classes? (packing common bases problem NP-complete)

Getting hardness under the oracle model is one thing; showing NP-hardness (or NP-completeness) for explicit, concrete representations is another. The authors also show that the abstract packing problem contains NP-complete problems as special cases. Concretely:

  • Even when k=2, the decision problem “can E be partitioned into two common bases?” includes NP-complete special cases.

  • One such setting: one matroid is a partition matroid (a very simple, structured class), while the other matroid is linear and given by an explicit matrix representation. In this case the problem already captures NP-complete problems. Thus there are explicit, compact representations of matroids for which the k=2 case is NP-complete.

Put differently, unless P = NP, there is no polynomial-time algorithm that always solves the partition-into-two-common-bases problem in these explicit settings. This complements the oracle lower bound with classical NP-hardness for natural representations.

How do reductions to NAE-SAT and Perfect Even Factor work for packing common bases? (How do reductions to NAE-SAT and Perfect Even Factor work?)

To prove their NP-hardness and hardness-in-the-oracle-model results the authors build reductions from well-known NP-complete problems and from combinatorial problems known to be hard. Two of the key sources are:

  • NAE-SAT (Not-All-Equal SAT): this is a variant of Boolean satisfiability where each clause must contain at least one true and at least one false literal. NAE-SAT is a canonical NP-complete problem, and it naturally encodes parity and partition-like constraints. The authors construct matroid gadgets that simulate variables and clauses so that a partition into common bases corresponds to a satisfying NAE assignment.

  • Perfect Even Factor in directed graphs: this is a problem about finding a certain 2-regular subgraph with parity constraints; it is closely related to cycle covers. The authors show how packing common bases can encode the existence of such structures, again via carefully designed matroid constructions. This links packing common bases to classical graph-factor problems.

At a high level, the reductions map logical and parity constraints into the combinatorial constraints of two matroids. One matroid enforces local constraints per gadget (e.g., “choose exactly one element from this set”), while the other matroid enforces global compatibility (e.g., “selected elements must satisfy parity across gadgets”). The interplay between these constraints forces any partition into common bases to correspond to a solution of the original NP-hard problem.

Technical takeaway about the complexity of packing common bases in matroids (common bases complexity summary)

To summarize the technical message:

  • Oracle hardness: There is no algorithm that, using only polynomially many independence/rank queries, can always decide whether two matroids can be partitioned into k common bases (even for k=2).

  • NP-hardness in explicit representations: The problem includes NP-complete problems as special cases (e.g., via reductions from NAE-SAT and Perfect Even Factor), so there are explicit, efficiently describable matroid pairs where deciding a partition into two common bases is NP-complete.

  • Consequently: both information-theoretic and computational barriers exist — you cannot hope for a single unified polynomial-time algorithm that solves packing common bases in full generality, either in the black-box oracle model or for concrete representations.

What are the practical implications for graph and matrix problems related to packing common bases? (practical implications for graph and matrix problems)

Why should non-theorists care? Packing common bases is a very general framework that subsumes or relates to many natural combinatorial problems. Here are a few concrete implications:

  • Graph decompositions: many graph packing problems (edge-disjoint spanning trees, dijoins, cycle covers) can be cast as packing bases in appropriate matroids. The hardness results imply that certain decomposition or packing tasks in graphs may be computationally intractable in their full generality, explaining why some long-standing conjectures resist algorithmic resolution.

  • Matrix and linear-algebraic decompositions: when matroids come from linear representations (columns of a matrix), partitioning into common bases can correspond to splitting columns into sets that each form a basis simultaneously for two different vector-space constraints. This can model resource allocation in networks, coding theory, or design of experiments. The NP-hardness result warns that many natural-sounding linear partitioning problems are likely hard.

  • Algorithm design guidance: since general algorithms are unlikely, focus should shift to special cases that remain tractable: restricted matroid classes, approximation or parameterized algorithms, randomized or heuristic methods, or fixed-parameter tractable regimes where complexity depends on small parameters.

Open problems and implications for conjectures about packing common bases (packing common bases problem future directions)

Although the paper closes some doors, it also clarifies promising directions:

  • Identify natural matroid classes where packing common bases is polynomial-time solvable. For example, when both matroids are graphic, or one is uniform and the other is graphic, what can be done? The paper suggests careful attention to representability and structure matters.

  • Study approximation or relaxed versions: can we find near-partitions or cover most elements with common bases efficiently?

  • Explore parameterized complexity: can the problem be solved efficiently when parameterized by treewidth of an associated graph, number of partitions k, or other structural measures?

  • Use hardness as a guide for combinatorial conjectures: the negative results explain why a single elegant characterization of k-packings for arbitrary matroid pairs is unlikely. Conjectures like Woodall’s or Rota’s can remain true, but algorithmic certification in the full generality may be out of reach.

Final perspective on the complexity of packing common bases in matroids (packing common bases big picture)

Bérczi and Schwarcz deliver a clear message: the problem of partitioning the ground set into common bases of two matroids is more than a technical curiosity — it is a robust source of computational hardness that bridges matroid theory, graph theory, and classic NP-complete problems. As of 2023, both oracle-model impossibility results and explicit NP-hard instances mean researchers should expect fundamental limits on general algorithms for this task.

If you work on graph decompositions, matrix partitioning, or matroid algorithms, this paper is a reminder: seek structure in your instances, exploit special matroid classes, or resign yourself to heuristics and parameterized methods when faced with the full generality of packing common bases.

Read the original paper here: https://arxiv.org/abs/1903.03579

Post Views: 923