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 combi ...

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

matroid In combinatorics, a branch of mathematics, 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 axiomatically, the most significant being ...

. The problem was formulated by as a common generalization of

graph matching Graph matching is the problem of finding a similarity between graphs.Endika Bengoetxea"Inexact Graph Matching Using Estimation of Distribution Algorithms" Ph. D., 2002Chapter 2:The graph matching problem(retrieved June 28, 2017) Graphs are comm ...

and

matroid intersection In combinatorial optimization, the matroid intersection problem is to find a largest common independent set in two matroids over the same ground set. If the elements of the matroid are assigned real weights, the weighted matroid intersection proble ...

. 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 described as the multiset analogue of the matroid. Definition Let E be a finite set and f: 2^E\rig ...

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

polynomial time In 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 performed by ...

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, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

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 ...

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 (discrete mathematics), graph G on a surface (mathematics), surface \Sigma is a representation of G on \Sigma in which points of \Sigma are associated with graph the ...

s of maximum genus. These 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 conta ...

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 whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...

, with

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

), the

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

s (in which the elements are edges in an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

, 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 ''capaci ...

s (in which the elements belong to a family of

disjoint sets In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. A ...

, 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 Rank is the relative position, value, worth, complexity, power, importance, authority, level, etc. of a person or object within a ranking, such as: Level or position in a hierarchical organization * Academic rank * Diplomatic rank * Hierarchy * H ...

(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 num ...

. In particular, using a matrix multiplication algorithm of Le Gall, 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)

. 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 matrices. ...

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 m elements is an m \times 1 matrix consisting of a single column of m 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 n, c ...

s in a

matrix Matrix most commonly refers to: * ''The Matrix'' (franchise), an American media franchise ** ''The Matrix'', a 1999 science-fiction action film ** "The Matrix", a fictional setting, a virtual reality environment, within ''The Matrix'' (franchis ...

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 m ...

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, i.e. in the problem of determining whether a given multivariate polynomi ...

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 value that is a function of the entries of a square matrix. It characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and ...

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 mathematics, in particular linear algebra, the Sherman–Morrison formula, named after Jack Sherman and Winifred J. Morrison, computes the inverse of the sum of an invertible matrix A and the outer product, u v^\textsf, of vectors u and v. Th ...

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 algorithms are known, with running time

O(mn\log^6 n)

on graphs with

m

vertices and

n

edges. For simple graphs,

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 more ...

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 maximizing a criterion among a number of candidate so ...

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 insta ...

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 is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...

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 cliq ...

, 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

, 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. , 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 Co ...

, 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'' 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 Venkatesan ...

, mr = 963159 , pages = 523–534 , title = Finding a maximum-genus graph imbedding , volume = 35 , year = 1988, s2cid = 17991210 {{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. It started in 1981, with László Babai and László Lovász as the editors-in-chief with Paul Erdős as honorar ...

, 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 , 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 , title = 12th International Colloquium on Automata, Languages, and Programming (ICALP), Nafplion, Greece, July 15–19, 1985 , volume = 194 , year = 1985, isbn = 978-3-540-15650-5 {{citation , last1 = Jensen , first1 = Per M. , last2 = Korte , first2 = Bernhard , author2-link = Bernhard Korte , doi = 10.1137/0211014 , issue = 1 , 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 is ...

, mr = 646772 , pages = 184–190 , title = Complexity of matroid property algorithms , volume = 11 , year = 1982 {{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 {{citation , last = Le Gall , first = François , contribution = Powers of tensors and fast matrix multiplication , doi = 10.1145/2608628.2608664 , location = New York , mr = 3239939 , pages = 296–303 , publisher = ACM , title = Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation (ISSAC 2014) , year = 2014, isbn = 9781450325011 , s2cid = 2597483 {{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 applicat ...

, 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 , 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 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 i ...