combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combina ...

, the matroid parity problem is a problem of finding the largest independent set of paired elements in a

matroid In combinatorics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid Axiomatic system, axiomatically, the most significant being in terms ...

. The problem was formulated by as a common generalization of graph matching and matroid intersection. It is also known as

polymatroid In mathematics, a polymatroid is a polytope associated with a submodular function. The notion was introduced by Jack Edmonds in 1970. It is also a generalization of the notion of a matroid. Definition Polyhedral definition Let E be a finite set ...

matching, or the matchoid problem. Matroid parity can be solved in

polynomial time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

for

linear matroid In the mathematical theory of matroids, a matroid representation is a family of vectors whose linear independence relation is the same as that of a given matroid. Matroid representations are analogous to group representations; both types of repre ...

s. However, it is

NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

for certain compactly-represented matroids, and requires more than a polynomial number of steps in the

matroid oracle In mathematics and computer science, a matroid oracle is a subroutine through which an algorithm may access a matroid, an abstract combinatorial structure that can be used to describe the linear dependencies between vectors in a vector space or th ...

model. Applications of matroid parity algorithms include finding large planar subgraphs and finding

graph embedding In topological graph theory, an embedding (also spelled imbedding) of a graph G on a surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with vertices and simple arcs (homeomorphic images of ,1/math>) ...

s of maximum genus. Matroid parity algorithms can also be used to find connected dominating sets and

feedback vertex set In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles ("removal" means deleting the vertex and all edges adjacent to it). Equivalently, each FVS con ...

s in graphs of maximum degree three.

Formulation

can be defined from a

finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, is a finite set with five elements. Th ...

of elements and from a notion of what it means for subsets of elements to be independent, subject to the following constraints: *Every subset of an independent set should be independent. *If

S

and

T

are independent sets, with

, T, >, S,

, then there exists an element

t\in T

such that

S\cup\

is independent. Examples of matroids include the

s (in which the elements are vectors in a

vector space In mathematics and physics, a vector space (also called a linear space) is a set (mathematics), set whose elements, often called vector (mathematics and physics), ''vectors'', can be added together and multiplied ("scaled") by numbers called sc ...

, with

linear independence In the theory of vector spaces, a set (mathematics), set of vector (mathematics), vectors is said to be if there exists no nontrivial linear combination of the vectors that equals the zero vector. If such a linear combination exists, then th ...

), the

graphic matroid In the mathematical theory of Matroid theory, matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the tree (graph theory), forests in a given finite undirected graph. The dual matr ...

s (in which the elements are edges in an

undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

, independent when they contain no cycle), and the

partition matroid In mathematics, a partition matroid or partitional matroid is a matroid that is a direct sum of uniform matroids. It is defined over a base set in which the elements are partitioned into different categories. For each category, there is a ''capa ...

s (in which the elements belong to a family of

disjoint sets In set theory in mathematics and Logic#Formal logic, formal logic, two Set (mathematics), sets are said to be disjoint sets if they have no element (mathematics), element in common. Equivalently, two disjoint sets are sets whose intersection (se ...

, and are independent when they contain at most one element in each set). Graphic matroids and partition matroids are special cases of linear matroids. In the matroid parity problem, the input consists of a matroid together with a pairing on its elements, so that each element belongs to one pair. The goal is to find a subset of the pairs, as large as possible, so that the union of the pairs in the chosen subset is independent. Another seemingly more general variation, in which the allowable pairs form a graph rather than having only one pair per element, is equivalent: an element appearing in more than one pair could be replaced by multiple copies of the element, one per pair.

Algorithms

The matroid parity problem for linear matroids can be solved by a

randomized algorithm A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...

in time

O(nr^)

, where

n

is the number of elements of the matroid,

r

is its

rank A rank is a position in a hierarchy. It can be formally recognized—for example, cardinal, chief executive officer, general, professor—or unofficial. People Formal ranks * Academic rank * Corporate title * Diplomatic rank * Hierarchy ...

(the size of the largest independent set), and

\omega

is the exponent in the time bounds for

fast matrix multiplication In theoretical computer science, the computational complexity of matrix multiplication dictates how quickly the operation of matrix multiplication can be performed. Matrix multiplication algorithms are a central subroutine in theoretical and nu ...

. In particular, using a matrix multiplication algorithm of

Virginia Vassilevska Williams Virginia Vassilevska Williams (née Virginia Panayotova Vassilevska) is a theoretical computer scientist and mathematician known for her research in computational complexity theory and algorithms. She is currently the Steven and Renee Finn Care ...

et al., it can be solved in time

O(nr^)

. Without using fast matrix multiplication, the linear matroid parity problem can be solved in time

O(nr^2)

. It is also possible to find a minimum-weight solution to the matroid parity problem, or a maximum-weight paired independent set, in linear matroids, in time

O(n^3r)

. These algorithms are based on a

linear algebra Linear algebra is the branch of mathematics concerning linear equations such as :a_1x_1+\cdots +a_nx_n=b, linear maps such as :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n, and their representations in vector spaces and through matrix (mathemat ...

formulation of the problem by . Suppose that an input to the problem consists of

m

pairs of

r

-dimensional vectors (arranged as

column vector In linear algebra, a column vector with elements is an m \times 1 matrix consisting of a single column of entries, for example, \boldsymbol = \begin x_1 \\ x_2 \\ \vdots \\ x_m \end. Similarly, a row vector is a 1 \times n matrix for some , c ...

s in a

matrix Matrix (: matrices or matrixes) or MATRIX may refer to: Science and mathematics * Matrix (mathematics), a rectangular array of numbers, symbols or expressions * Matrix (logic), part of a formula in prenex normal form * Matrix (biology), the m ...

M

of size

r\times 2m

). Then the number of pairs in the optimal solution is :

\frac\operatorname\begin0&M\\M^T&T\end -m,

where

T

is a

block diagonal matrix In mathematics, a block matrix or a partitioned matrix is a matrix that is interpreted as having been broken into sections called blocks or submatrices. Intuitively, a matrix interpreted as a block matrix can be visualized as the original matrix w ...

whose blocks are

2\times 2

submatrices of the form :

\begin0&t_i\\-t_i&0\end

for a sequence of variables

t_1,\dots t_m

. The

Schwartz–Zippel lemma In mathematics, the Schwartz–Zippel lemma (also called the DeMillo–Lipton–Schwartz–Zippel lemma) is a tool commonly used in probabilistic polynomial identity testing. Identity testing is the problem of determining whether a given multivaria ...

can be used to test whether this matrix has full rank or not (that is, whether the solution has size

r/2

or not), by assigning random values to the variables

t_i

and testing whether the resulting matrix has

determinant In mathematics, the determinant is a Scalar (mathematics), scalar-valued function (mathematics), function of the entries of a square matrix. The determinant of a matrix is commonly denoted , , or . Its value characterizes some properties of the ...

zero. By applying a

greedy algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...

that removes pairs one at a time by setting their indeterminates to zero as long as the matrix remains of full rank (maintaining the inverse matrix using the

Sherman–Morrison formula In linear algebra, the Sherman–Morrison formula, named after Jack Sherman and Winifred J. Morrison, computes the inverse of a "rank-1 update" to a matrix whose inverse has previously been computed. That is, given an invertible matrix A and the ...

to check the rank after each removal), one can find a solution whenever this test shows that it exists. Additional methods extend this algorithm to the case that the optimal solution to the matroid parity problem has fewer than

r/2

pairs. For graphic matroids, more efficient matroid parity algorithms are known, based on

range searching In computer science, the range searching problem consists of processing a set ''S'' of objects, in order to determine which objects from ''S'' intersect with a query object, called the ''range''. For example, if ''S'' is a set of points correspond ...

data structures, with running time

O(mn\log^6 n)

on graphs with

m

vertices and

n

edges. For

simple graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a Set (mathematics), set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called ''Ver ...

m

O(n^2)

, but for

multigraph In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by mor ...

s, it may be larger, so it is also of interest to have algorithms with smaller or no dependence on

m

and worse dependence on

n

. In these cases, it is also possible to solve the graphic matroid parity problem in randomized expected time

O(n^4)

, or in time

O(n^3)

when each pair of edges forms a path. Although the matroid parity problem is

for arbitrary matroids, it can still be approximated efficiently. Simple

local search algorithm In computer science, local search is a heuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution that maximizes a criterion among a number of candida ...

s provide a

polynomial-time approximation scheme In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an inst ...

for this problem, and find solutions whose size, as a fraction of the optimal solution size, is arbitrarily close to one. The algorithm starts with the

empty set In mathematics, the empty set or void set is the unique Set (mathematics), set having no Element (mathematics), elements; its size or cardinality (count of elements in a set) is 0, zero. Some axiomatic set theories ensure that the empty set exi ...

as its solution, and repeatedly attempts to increase the solution size by one by removing at most a constant number

C

of pairs from the solution and replacing them by a different set with one more pair. When no more such moves are possible, the resulting solution is returned as the approximation to the optimal solution. To achieve an approximation ratio of

1-\epsilon

, it suffices to choose

C

to be approximately

5^

Applications

Many other optimization problems can be formulated as linear matroid parity problems, and solved in polynomial time using this formulation.

Hardness

The

clique problem In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which c ...

, of finding a

k

-vertex complete subgraph in a given

n

-vertex graph

G

, can be transformed into an instance of matroid parity as follows. Construct a

paving matroid In the mathematical theory of matroids, a paving matroid is a matroid in which every circuit has size at least as large as the matroid's rank. In a matroid of rank r every circuit has size at most r+1, so it is equivalent to define paving matroids ...

2n

elements, paired up so that there is one pair of elements per pair of vertices. Define a subset

S

of these elements to be independent if it satisfies any one of the following three conditions: *

S

has fewer than

2k

elements. *

S

has exactly

2k

elements, but is not the union of

k

pairs of elements. *

S

is the union of

k

pairs of elements that form a clique in

G

. Then there is a solution to the matroid parity problem for this matroid, of size

2k

, if and only if

G

has a clique of size

k

. Since finding cliques of a given size is NP-complete, it follows that determining whether this type of matrix parity problem has a solution of size

2k

is also NP-complete. This problem transformation does not depend on the structure of the clique problem in any deep way, and would work for any other problem of finding size-

k

subsets of a larger set that satisfy a computable test. By applying it to a randomly-permuted graph that contains exactly one clique of size

k

, and applying

Yao's principle In computational complexity theory, Yao's principle (also called Yao's minimax principle or Yao's lemma) relates the performance of randomized algorithms to deterministic (non-random) algorithms. It states that, for certain classes of algorithms, ...

relating expected and average-case complexity, one can show that any deterministic or randomized algorithm for matroid parity that accesses its matroid only by independence tests needs to make an exponential number of tests.

References

{{reflist, refs= {{citation , last1 = Călinescu , first1 = Gruia , last2 = Fernandes , first2 = Cristina G. , author2-link = Cristina G. Fernandes , last3 = Finkler , first3 = Ulrich , last4 = Karloff , first4 = Howard , doi = 10.1006/jagm.1997.0920 , issue = 2 , journal = Journal of Algorithms , mr = 1622397 , pages = 269–302 , title = A better approximation algorithm for finding planar subgraphs , volume = 27 , year = 1998, citeseerx = 10.1.1.47.4731 , s2cid = 8329680 . {{citation , last1 = Cheung , first1 = Ho Yee , last2 = Lau , first2 = Lap Chi , last3 = Leung , first3 = Kai Man , doi = 10.1145/2601066 , issue = 3 , journal =

ACM Transactions on Algorithms ''ACM Transactions on Algorithms'' (''TALG'') is a quarterly peer-reviewed scientific journal covering the field of algorithms. It was established in 2005 and is published by the Association for Computing Machinery. The editor-in-chief is Edith Coh ...

, mr = 3233690 , pages = 10:1–10:26 , title = Algebraic algorithms for linear matroid parity problems , url = https://cs.uwaterloo.ca/~lapchi/papers/parity.pdf , volume = 10 , year = 2014, citeseerx = 10.1.1.194.604 , s2cid = 894004 {{citation , last = Speckenmeyer , first = E. , contribution = Bounds on feedback vertex sets of undirected cubic graphs , mr = 875903 , pages = 719–729 , publisher = North-Holland , location = Amsterdam , series = Colloquia Mathematica Societatis János Bolyai , title = Algebra, Combinatorics and Logic in Computer Science, Vol. I, II (Győr, 1983) , volume = 42 , year = 1986 {{citation , last = Lawler , first = Eugene L. , authorlink = Eugene Lawler , contribution = Chapter 9: The Matroid Parity Problem , contribution-url = https://books.google.com/books?id=MTuoAAAAQBAJ&pg=PA356 , location = New York , mr = 0439106 , pages = 356–367 , publisher = Holt, Rinehart and Winston , title = Combinatorial Optimization: Networks and Matroids , year = 1976 {{citation , last1 = Furst , first1 = Merrick L. , last2 = Gross , first2 = Jonathan L. , last3 = McGeoch , first3 = Lyle A. , doi = 10.1145/44483.44485 , issue = 3 , journal =

Journal of the ACM The ''Journal of the ACM'' (''JACM'') is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief is ...

, mr = 963159 , pages = 523–534 , title = Finding a maximum-genus graph imbedding , volume = 35 , year = 1988, s2cid = 17991210 , doi-access = free {{citation , last1 = Geelen , first1 = James , author1-link = Jim Geelen , last2 = Iwata , first2 = Satoru , doi = 10.1007/s00493-005-0013-7 , issue = 2 , journal =

Combinatorica ''Combinatorica'' is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science Computer science is the study of computation, information, and automation. Computer science spans Theore ...

, mr = 2127610 , pages = 187–215 , title = Matroid matching via mixed skew-symmetric matrices , volume = 25 , year = 2005, citeseerx = 10.1.1.702.5431 , s2cid = 18576135 {{citation , last1 = Gabow , first1 = Harold N. , author1-link = Harold N. Gabow , last2 = Stallmann , first2 = Matthias , title = Automata, Languages and Programming , editor-last = Brauer , editor-first = Wilfried , contribution = Efficient algorithms for graphic matroid intersection and parity (extended abstract) , doi = 10.1007/BFb0015746 , location = Berlin , mr = 819256 , pages = 210–220 , publisher = Springer , series = Lecture Notes in Computer Science , volume = 194 , year = 1985, isbn = 978-3-540-15650-5 {{citation , last1 = Iwata , first1 = Satoru , last2 = Kobayashi , first2 = Yusuke , arxiv = 1905.13371 , doi = 10.1137/17M1141709 , issue = 2 , journal =

SIAM Journal on Computing The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation i ...

, mr = 4413075 , pages = STOC17-238 – STOC17-280 , title = A weighted linear matroid parity algorithm , volume = 51 , year = 2022 {{citation , last1 = Jensen , first1 = Per M. , last2 = Korte , first2 = Bernhard , author2-link = Bernhard Korte , doi = 10.1137/0211014 , issue = 1 , journal =

, mr = 646772 , pages = 184–190 , title = Complexity of matroid property algorithms , volume = 11 , year = 1982 {{citation , last = Jordán , first = Tibor , editor1-last = Katona , editor1-first = Gyula O. H. , editor1-link = Gyula O. H. Katona , editor2-last = Schrijver , editor2-first = Alexander , editor2-link = Alexander Schrijver , editor3-last = Szőnyi , editor3-first = Tamás , contribution = Rigid and globally rigid graphs with pinned vertices , contribution-url = https://egres.elte.hu/tr/egres-09-05.pdf , doi = 10.1007/978-3-642-13580-4_7 , mr = 2797964 , pages = 151–172 , publisher = János Bolyai Mathematical Society and Springer , series = Bolyai Society Mathematical Studies , title = Fete of combinatorics and computer science: Papers from the conference to commemorate the 60th birthday of László Lovász held in Keszthely, August 11–15, 2008 , volume = 20 , year = 2010, isbn = 978-3-642-13579-8 {{citation , last = Soto , first = José A. , arxiv = 1102.3491 , doi = 10.1016/j.dam.2012.10.019 , issue = part 2 , journal =

Discrete Applied Mathematics ''Discrete Applied Mathematics'' is a peer-reviewed scientific journal covering algorithmic and applied areas of discrete mathematics. It is published by Elsevier and the editor-in-chief is Endre Boros (Rutgers University). The journal was split ...

, mr = 3159127 , pages = 406–412 , title = A simple PTAS for weighted matroid matching on strongly base orderable matroids , volume = 164 , year = 2014, s2cid = 17970404 {{citation , last = Lovász , first = L. , authorlink = László Lovász , doi = 10.1016/0095-8956(80)90066-0 , issue = 2 , journal =

Journal of Combinatorial Theory The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicati ...

, mr = 572475 , pages = 208–236 , series = Series B , title = Matroid matching and some applications , volume = 28 , year = 1980, doi-access = free {{citation , last1 = Lee , first1 = Jon , author1-link = Jon Lee (mathematician) , last2 = Sviridenko , first2 = Maxim , last3 = Vondrák , first3 = Jan , doi = 10.1137/11083232X , issue = 1 , journal =

, mr = 3033132 , pages = 357–379 , title = Matroid matching: the power of local search , volume = 42 , year = 2013, citeseerx = 10.1.1.600.4878 {{citation , last1 = Ueno , first1 = Shuichi , last2 = Kajitani , first2 = Yoji , last3 = Gotoh , first3 = Shin'ya , department = Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986) , doi = 10.1016/0012-365X(88)90226-9 , issue = 1–3 , journal =

Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

, mr = 975556 , pages = 355–360 , title = On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three , volume = 72 , year = 1988, doi-access = free {{citation , last1=Vassilevska Williams , first1=Virginia , last2=Xu , first2=Yinzhan , last3=Xu , first3=Zixuan , last4=Zhou , first4=Renfei , contribution=New bounds for matrix multiplication: from alpha to omega , title=Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , date=2024 , pages=3792–3835 , arxiv=2307.07970 , doi=10.1137/1.9781611977912.134, isbn=978-1-61197-791-2 Combinatorial optimization

Intersection In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their ...