Egerváry Research Groupon Combinatorial Optimization

Technical reportS
TR-2021-08. Published by the Egerváry Research Group, Pázmány P. sétány 1/C,
H–1117, Budapest, Hungary. Web site: www.cs.elte.hu/egres . ISSN 1587–4451.

Approximation by LexicographicallyMaximal Solutions in Matching andMatroid Intersection Problems
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi,
and Yu Yokoi

July 2021

Approximation by Lexicographically Maximal
Solutions in Matching and Matroid Intersection
Problems
Kristóf Bérczia

Tamás Királyb

Yutaro Yamaguchic

Yu Yokoid

July 2021

Abstract
We study how good a lexicographically maximal solution is in the weighted
matching and matroid intersection problems. A solution is lexicographicallymaximal if it takes as many heaviest elements as possible, and subject to this,it takes as many second heaviest elements as possible, and so on. If the distinct
weight values are sufficiently dispersed, e.g., the minimum ratio of two distinct
weight values is at least the ground set size, then the lexicographical maximality
and the usual weighted optimality are equivalent. We show that the thresholdof the ratio for this equivalence to hold is exactly 2. Furthermore, we provethat if the ratio is less than 2, say α, then a lexicographically maximal solution
achieves (α/2)-approximation, and this bound is tight.

1

Introduction

Matching in bipartite graphs is one of the fundamental topics in combinatorics andoptimization. Due to its diverse applications, various optimality criteria of matchings
have been proposed based on the number of edges, the total weight of edges, etc. The
concept of rank maximality is one of them, which is especially studied in the context
of matching problems under preferences [2,7]. In this setting, we are given a partitiona

MTA-ELTE Momentum Matroid Optimization Research Group and MTA-ELTE Egerváry Research Group, Department of Operations Research, Eötvös Loránd University, Budapest, Hungary.
Email: kristof.berczi@ttk.elte.hu.
b
MTA-ELTE Momentum Matroid Optimization Research Group and MTA-ELTE Egerváry Research Group, Department of Operations Research, Eötvös Loránd University, Budapest, Hungary.
Email: tamas.kiraly@ttk.elte.hu.
cDepartment of Informatics, Faculty of Information Science and Electrical Engineering, Kyushu
University, Fukuoka, Japan. Email: yutaro yamaguchi@inf.kyushu-u.ac.jp.
dPrinciples of Informatics Research Division, National Institute of Informatics, Tokyo, Japan.
Email: yokoi@nii.ac.jp.

12

Section 2. Results{E1 , E2 , . . . , Ek } of the edge set E that represents a priority order, and a matchingM ⊆ E is rank-maximal if |M ∩ E1 | is maximized, and subject to this, |M ∩ E2 |is maximized, and so on. As pointed out in several papers [1, 2, 4, 7] (on generalized
problems), the problem of finding a rank-maximal solution can be reduced to the usual
weight-maximization setting by using sufficiently dispersed weights, e.g., by assigning|E|k−i for each element in Ei . (Clearly, it is not enough to assign arbitrary weightsthat are consistent with the priority order.)In this paper, we explore the relation between rank-maximality and optimality inthe weighted setting for two generalizations of bipartite matching: matching in generalgraphs and matroid intersection. To avoid confusion, we hereafter replace the term
“rank” with “lex(icographical)” because we also deal with ranks in matroids. The
main results of the paper (Theorems 2.1 and 2.2) state that, in both problems, theequivalence between lex-maximality and weighted optimality holds if the minimum
ratio of two distinct weight values is larger than 2. This implies that we can choose
the base of exponential weights as any constant larger than 2 (instead of |E|) in the
aforementioned reduction. Furthermore, we show that if the minimum ratio is at most2, say α, then a lex-maximal solution achieves (α/2)-approximation of the maximum
weight, and this bound is tight.

2

Results

We assume the basic notation and terminology on graphs and matroids (see, e.g., [8]).
Throughout the paper, let E be a finite ground set and w : E → R>0 be a positive
weight function on E. For a subset X ⊆ E, the weight w(X) is defined as the sum of
its elements. Let w1 , w2 , . . . , wk be the distinct values of w in descending order. We
assume k ≥ 2 (otherwise, the results are trivial), and definewi.
1≤i≤k−1 wi+1

αw := minFor a subset X ⊆ E and 1 ≤ i ≤ k, we denote by Xi = { e ∈ X | S
w(e) = wi }the restriction of X to the elements of weight wi , and define X≤i := j≤i Xj andaccordingly X≥i , X<i , and X>i . For two subsets X, Y ⊆ E, we say that X is lex-larger
than Y (or Y is lex-smaller than X) if there exists an index i such that |Xj | = |Yj | forany j < i and |Xi | > |Yi |. For a family F ⊆ 2E of subsets of E, we say that X ∈ F islex-maximal if no Y ∈ F is lex-larger than X. Note that a lex-maximal subset X ∈ F
may not be unique but the sequence |X1 |, |X2 |, . . . , |Xk | is unique.
A weighted matching instance consists of an undirected graph G = (V, E) and aweight function w on the edge set. We denote by opt(G, w) the optimal value, i.e.,the maximum weight of a matching in G. In addition, we denote by lexopt(G, w)
the weight of a lex-maximal matching in G (where F is the family of matchings inG), which takes as many edges of weight w1 as possible, and subject to this, takes as
many edges of weight w2 as possible, and so on.
A weighted matroid intersection instance consists of two matroids M1 = (E, I1 )and M2 = (E, I2 ) and a weight function w on the common ground set. We denote by
EGRES Technical Report No. 2021-08

3

Section 3. Proofs

opt(M1 , M2 , w) the optimal value, i.e., the maximum weight of a common independent
set in I1 ∩I2 . In addition, we denote by lexopt(M1 , M2 , w) the weight of a lex-maximal
common independent set (where F = I1 ∩I2 ), which takes as many elements of weight
w1 as possible, and subject to this, takes as many elements of weight w2 as possible,
and so on.
The main theorems are stated as follows.
Theorem 2.1. Let (G, w) be a weighted matching instance. If αw ≤ 2, thenlexopt(G, w) ≥αw
· opt(G, w).
2

Otherwise, a lex-maximal matching is a maximum-weight matching, and vice versa.
Theorem 2.2. Let (M1 , M2 , w) be a weighted matroid intersection instance. If αw ≤2, thenαw· opt(M1 , M2 , w).
lexopt(M1 , M2 , w) ≥2
Otherwise, a lex-maximal common independent set is a maximum-weight common
independent set, and vice versa.
We remark that the approximation ratio is tight as the weighted bipartite matchingproblem is included as a common special case. Let G = (V, E) be a bipartite graphwith V = {1, 2, 3, 4} and E = { e1 = {1, 3}, e2 = {2, 3}, e3 = {2, 4} }. Definew(e1 ) = 1, w(e2 ) = x ∈ (1, 2], and w(e3 ) = 1. We then have αw = x (as w1 = x and
w2 = 1), opt(G, w) = 2, and lexopt(G, w) = x.

3

ProofsWe prove both theorems using the same strategy. The key definition and lemmas are
as follows.
Definition 3.1. Let X ⊆ E be a feasible solution that is not lex-maximal in aweighted matching or matroid intersection instance, and i be the smallest index suchthat X≤i is not lex-maximal in the restricted instance whose ground set is E≤i . We
say that a feasible solution Y ⊆ E in the original instance is eligible if the following
three conditions are satisfied: |Yj | = |Xj | for any j < i,
 |Yi | = |Xi | + 1, and |X>i \ Y>i | ≤ 2.

Intuitively, an eligible solution lexicographically improves the original solution at
the most significant improvable class by sacrificing at most two lighter elements.
Lemma 3.2. For any weighted matching instance (G, w) and any matching X thatis not lex-maximal, there exists an eligible matching Y .
EGRES Technical Report No. 2021-08

3.1

4

Matching: Proof of Lemma 3.2

Lemma 3.3. For any weighted matroid intersection instance (M1 , M2 , w) and any
common independent set X that is not lex-maximal, there exists an eligible common
independent set Y .
We here prove Theorems 2.1 and 2.2 using Lemmas 3.2 and 3.3, whose proofs are
given later.
Proof of Theorems 2.1 and 2.2. Let X ∗ be an optimal solution. Starting with X =X ∗ , we repeatedly update X to an eligible Y until it becomes lex-maximal. Let Y ∗be the lex-maximal solution that is finally obtained.
In any update from X to Y , we havew(Y ) = w(Y≤i ) + w(Y>i ) ≥ w(X≤i ) + wi + w(X>i ) − 2wi+1 ≥ w(X) −2 − αw· wi .
αw

If αw > 2, then we have w(Y ) > w(X), which cannot happen at the beginning when
X = X ∗ . Thus, X ∗ is lex-maximal. As any lex-maximal solution has the same weight,
we also see that any lex-maximal solution is optimal, and we are done for the second
statements.
Suppose that αw ≤ 2. Since we always have |Yj | = |Xj | = |Yj∗ | (j < i) and|Yi | = |Xi | + 1 ≤ |Yi∗ |, we see that i is nondecreasing during the process and each wi
appears in the right-hand side at most |Yi∗ | times in total. Thus, by repeating theabove inequalities, we obtaink

2 − αw X
2 − αw
w(Y ) ≥ w(X ) −· w(Y ∗ ),(wi · |Yi∗ |) = w(X ∗ ) −αw i=1αw∗∗

which implies the first statements.

3.1

Matching: Proof of Lemma 3.2

We prove Lemma 3.2 by contradiction.1 Suppose to the contrary that there exists a
counterexample, and take a minimal one in the following sense. First, the ground set
E is minimized as the first priority, and subject to this, a counterexample matching
X (that is not lex-maximal but admits no eligible matching Y ) and a lex-maximal
matching Z are taken so that the symmetric difference X4Z = (X \ Z) ∪ (Z \ X) is
minimized.
By the minimality, we have E = X ∪ Z = X4Z. Indeed, if there exists an edgee ∈ E \ (X ∪ Z), then we obtain a smaller counterexample by removing e (no eligible
matching can newly appear), a contradiction. Similarly, if there exists e ∈ X ∩ Z,
then we obtain a smaller counterexample again by removing e (note that no edge isadjacent to e as X and Z are matchings), a contradiction.
Claim 3.4. There are no adjacent edges of the heaviest weight.
1

We could give an algorithmic proof similar to the matroid intersection case in the next section,
but we here describe an alternative proof because it is slightly simpler and may be extended to otherproblems.

EGRES Technical Report No. 2021-08

3.2

Matroid Intersection: Proof of Lemma 3.3

5

Proof. Suppose to the contrary that e1 = {v, u1 } ∈ X and e2 = {v, u2 } ∈ Z areadjacent (at v) and w(e1 ) = w(e2 ) = w1 . If u1 = u2 (i.e., e1 and e2 are parallel),then X 0 = (X \ {e1 }) ∪ {e2 } is a smaller counterexample, a contradiction. Otherwise,
consider the instance obtained by contracting the two edges e1 and e2 , i.e., by merging
u1 and u2 into a single vertex, removing the vertex v together with the incident edges,
and restricting the weight function to the remaining set of edges.
As X is a matching that is not lex-maximal, this is true for X 0 = X \ {e1 } after
the contraction. By the minimality of the counterexample, there exists an eligible
matching Y 0 ⊆ E \ {e1 , e2 }. Since at most one of u1 and u2 is matched by Y 0 in
the original graph, we can add e1 or e2 to Y 0 to obtain a matching Y in the original
instance. Moreover, the Y thus obtained is eligible by definition even if e2 is addedsince e1 ∈ X≤i for any i ≥ 1, contradicting our indirect assumption.
Claim 3.5. X1 = ∅.
Proof. Suppose to the contrary that there exists an edge e ∈ X1 . Then, by Claim 3.4,
we have w(f ) < w(e) = w1 for each adjacent edge f ∈ Z. Thus, we can obtain alex-larger matching Z 0 from Z by adding e and by removing all the (at most two)
adjacent edges, a contradiction.
By Claim 3.5, we have |X1 | = 0 < |Z1 |. Let f ∈ Z be an edge with w(f ) = w1 .
Then, we can obtain an eligible matching Y from X by adding f and by removing
all the (at most two) adjacent edges, a contradiction. This concludes the proof of thelemma.

3.2

Matroid Intersection: Proof of Lemma 3.3

The proof relies on (the correctness of) an augmenting path algorithm for the weighted
matroid intersection problem, which was first described in [6]. We first review the basic
facts based on [8, Sections 41.2 and 41.3].
Let (M1 , M2 , w) be a weighted matroid intersection instance. For each matroid Mi(i ∈ {1, 2}), we denote the independent set family, the rank function, and the spanfunction2 by Ii ⊆ 2E , ri : 2E → Z≥0 , and spani : 2E → 2E , respectively. For a set X
and elements x ∈ X and y 6∈ X, we write X \ {x} and X ∪ {y} as X − x and X + y,respectively.
Let I ∈ I1 ∩ I2 be a common independent set. The exchangeability graph withrespect to I is a directed bipartite graph D = (E \ I, I; A) defined as follows. Let
A := A1 ∪ A2 , whereA1 := { (y, x) | x ∈ E \ I, y ∈ I, I + x − y ∈ I1 },A2 := { (x, y) | x ∈ E \ I, y ∈ I, I + x − y ∈ I2 }.
We also define
S := { s ∈ E \ I | I + s ∈ I1 },T := { t ∈ E \ I | I + t ∈ I2 },2This is also called the closure function; we follow the terminology of [8] for simplicity.

EGRES Technical Report No. 2021-08

3.2

Matroid Intersection: Proof of Lemma 3.3

6

where elements in S and in T are called sources and sinks, respectively. Note that A1and S depend only on M1 , and A2 and T depend only on M2 . Let c : E → R be acost function on the vertex set defined as follows:(w(e)(e ∈ I),c(e) :=(3.1)−w(e) (e ∈ E \ I).
An S–T path P in D is cheapest if the total cost of its vertices is minimized. Subject
to this, P is shortest if the number of its vertices is minimized.
For a nonnegative integer `, a common independent set I ∈ I1 ∩ I2 is said to be `extreme if w(I) is maximized subject to I ∈ I1 ∩ I2 and |I| = `. The following lemma
leads to a simple augmenting path algorithm for the weighted matroid intersection
problem. The key is that one can augment any `-extreme solution to some (` + 1)extreme solution (if exists) by simply exchanging elements along a path.
Lemma 3.6 (cf. [8, Theorems 41.3, 41.5, and 41.6]). Let I ∈ I1 ∩ I2 be an `-extreme
common independent set, and suppose that there exists a common independent set
J ∈ I1 ∩ I2 with |J| > |I|. Then, D contains an S–T path, which may consist of asingle vertex in S ∩ T . Let P be a shortest cheapest S–T path in D with respect tothe cost function c defined as (3.1). Then, no inner vertex of P is a source or a sink,and I4P is an (` + 1)-extreme common independent set.
Now we start the proof of Lemma 3.3. Let X ∈ I1 ∩ I2 be a common independent
set that is not lex-maximal, and let i be the smallest index such that X≤i is not
lex-maximal in the restricted instance whose ground set is E≤i .
Claim 3.7. There exists a common independent set Y 0 ⊆ E≤i such that |Yj0 | = |Xj |for any j < i, |Yi0 | = |Xi | + 1, span1 (X≤i ) ⊆ span1 (Y 0 ), and span2 (X≤i ) ⊆ span2 (Y 0 ).
Proof. Define an auxiliary weight function w0 : E≤i → R>0 by w0 (e) := ni−j for eache ∈ Ej (j = 1, 2, . . . , i), where n = |E≤i |. As remarked in the introduction, the lexicographical order coincides with the weighted order, i.e., for any two subsets Z, Z 0 ⊆ E≤i ,Z is lex-larger than Z 0 if and only if w0 (Z) > w0 (Z 0 ).
Let ` := |X≤i |. Then, X≤i is `-extreme in the restricted instance (M1 |E≤i , M2 |E≤i , w0 ),which has a larger common independent set. By Lemma 3.6, one can obtain an (`+1)extreme common independent set Y 0 ⊆ E≤i by flipping X≤i along a source-sink path
P in the exchangeability graph. Note that |Yj0 | = |Xj | for any j < i and |Yi0 | = |Xi |+1
by the choice of i and the definition of w0 .
If P consists of a single vertex (which is a source and a sink), then the claim
immediately follows since Y 0 = X≤i + y for some element y ∈ Ei . Otherwise, lets and t be the first and last vertices of P , respectively. By the definitions of theexchangeability graph and the sources and sinks, y ∈ span1 (X≤i ) ⊆ span1 (X≤i + s)
for every y ∈ P − s and y ∈ span2 (X≤i ) ⊆ span2 (X≤i + t) for every y ∈ P − t (recall
that any y ∈ P − s is not a source and any y ∈ P − t is not a sink). Hence, we have

EGRES Technical Report No. 2021-08

Section 4. Concluding Remarks

7

span1 (X≤i ∪ P ) = span1 (X≤i + s) and span2 (X≤i ∪ P ) = span2 (X≤i + t), and then
` + 1 = |Y 0 | = r1 (Y 0 )≤ r1 (X≤i ∪ P ) = r1 (X≤i + s)
≤ r1 (X≤i ) + r1 (s) = |X≤i | + 1 = ` + 1,
` + 1 = |Y 0 | = r2 (Y 0 )≤ r2 (X≤i ∪ P ) = r2 (X≤i + t)
≤ r2 (X≤i ) + r2 (t) = |X≤i | + 1 = ` + 1,
which implies that the equality holds everywhere. Thus we have span1 (Y 0 ) = span1 (X≤i +s) ⊇ span1 (X≤i ) and span2 (Y 0 ) = span2 (X≤i + t) ⊇ span2 (X≤i ), which completes theproof.
Take a subset Y 0 ⊆ E≤i satisfying the conditions in Claim 3.7. We then obtain
an eligible common independent set Y ⊆ E from Y 0 ∪ X>i by removing at mosttwo elements in X>i as follows. If r1 (Y 0 ∪ X>i ) = r2 (Y 0 ∪ X>i ) = |X| + 1, thenY 0 ∪ X>i ∈ I1 ∩ I2 and we do not need to remove any element. Suppose that r1 (Y 0 ∪X>i ) < |X|+1. As span1 (X≤i ) ⊆ span1 (Y 0 ), we have r1 (Y 0 ∪X>i ) ≥ r1 (X) = |X|, andhence r1 (Y 0 ∪ X>i ) = |X|. This implies that Y 0 ∪ X>i contains exactly one circuit ofM1 , which must intersect X>i since Y 0 ∈ I1 . Hence, there exists an element x ∈ X>isuch that Y 0 ∪ (X>i − x) ∈ I1 . The same holds for M2 . Thus we obtain a common
independent set Y ⊆ Y 0 ∪ X>i with |X>i \ Y>i | ≤ 2, which is eligible.

4

Concluding Remarks

In this paper, we have analyzed how good a lex-maximal solution is in the weighted
matching and matroid intersection problems based on how dispersed the distinct
weight values are. It is well-known that, subject to a single matroid, a lex-maximal
solution is always optimal, which can be found by a greedy algorithm. For more general independence systems, Jenkyns [3] and Korte and Hausmann [5] independently
analyzed the worst-case approximation ratio of a greedy algorithm. In particular, theworst ratio is 2 in the weighted matching and matroid intersection problems, whilea lex-maximal solution (which is a possible output of a greedy algorithm) always
achieves the maximum weight if the distinct weight values are sufficiently dispersed.
From this perspective, we have filled the gap between these two situations.
A natural question is as follows: how about a further (common) generalization,e.g., the weighted matroid parity problem? We just remark that it seems difficult
to extend our algorithmic proof straightforwardly bacause no counterpart of augmentation from any `-extreme solution to some (` + 1)-extreme solution along a path
(Lemma 3.6) is known. A minimal counterexample proof (like the matching case)also seems nontrivial; in particular, we have found no counterpart of Claim 3.4.

EGRES Technical Report No. 2021-08

8References

Acknowledgments
We are grateful to Naoyuki Kamiyama for giving comments on a literature on rankmaximal matchings.
Kristóf Bérczi was supported by the Lendület Programme of the Hungarian Academyof Sciences – grant number LP2021-1/2021 and by the Hungarian National Research,
Development and Innovation Office – NKFIH, grant number FK128673. Tamás Király
was supported by the Hungarian National Research, Development and Innovation Office – NKFIH, grant number K120254. Yutaro Yamaguchi was supported by JSPS
KAKENHI Grant Numbers JP20K19743 and JP20H00605 and by Overseas Research
Program in Graduate School of Information Science and Technology, Osaka University. Yu Yokoi was supported by JSPS KAKENHI Grant Number JP18K18004.
“Application Domain Specific Highly Reliable IT Solutions” project has been implemented with the support provided from the National Research, Development andInnovation Fund of Hungary, financed under the Thematic Excellence Programme
TKP2020-NKA-06 (National Challenges Subprogramme) funding scheme.

References[1] C.-C. Huang, N. Kakimura, and N. Kamiyama. Exact and approximation algorithms for weighted matroid intersection. Mathematical Programming, 177(12):85–112, 2019.
[2] R. W. Irving, T. Kavitha, K. Mehlhorn, D. Michail, and K. E. Paluch. Rankmaximal matchings. ACM Transactions on Algorithms (TALG), 2(4):602–610,
2006.
[3] T. A. Jenkyns. The efficacy of the “greedy” algorithm. In Proceedings of the 7thSoutheastern Conference on Combinatorics, Graph Theory and Computing, pages
341–350, 1976.
[4] N. Kamiyama. Matroid intersection with priority constraints. Journal of the
Operations Research Society of Japan, 56(1):15–25, 2013.
[5] B. Korte and D. Hausmann. An analysis of the greedy heuristic for independence
systems. In Annals of Discrete Mathematics, volume 2, pages 65–74. Elsevier,
1978.
[6] E. L. Lawler. Matroid intersection algorithms.
9(1):31–56, 1975.

Mathematical Programming,[7] D. Michail. Reducing rank-maximal to maximum weight matching. TheoreticalComputer Science, 389(1-2):125–132, 2007.
[8] A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer,
2003.

EGRES Technical Report No. 2021-08