(Unfortunately the symbol
of matroids clashes
with the symbol of matchings.
Given that matroid is our
protagonist, in this text, we
will use to represent a
matroid and use to
represent a matching.)
In our previous text, we've shown
the problem of finding the maximum
matching in a bipartite graph is
equivalent to finding the maximum
cardinality common independent set,
of two partition matroids defined
by the two bipartite sets.
Finding the maximum cardinality
common independent set of
and
could be an easy problem if
were a matroid, since
finding the maximum cardinality
common independent set becomes
finding a basis in
now, which is solvable by the
greedy algorithm described
here.
But
is generally not a matroid,
and the example of matching in
partite graph above does good
in showing that: Consider
the maximal matching
and the maximum matching
,
there's no element in
that we can use to augment .
So independent set exchange
property does not hold.
However, even if the problem
of maximum cardinality
common independent set cannot
be solved by greedy algorithm
directly, it need not be
unsolvable. When it comes to
the problem of maximum matching,
we are familiar with solving
it with Augmenting Path algorithm
or Hopcroft-Karp algorithm.
And when it comes to the case
of maximal cardinality common
independent set of any two
matroids, mathematician
found it to be solvable by
reducing it to multiple
iterations of finding
augmenting path in a
delicately constructed
bipartite graph per iteration.
In this way, matroid theory
not only generalizes the
problem of maximum matching
into the language of matroids
but also leverages and
generalizes the methodology
of finding maximum matchings
in graph theory, into solving
the maximum cardinality
common independent set of
two general matroids, not
limited to the
partition matroids.
To prove the correctness of
our algorithm to find the
maximum cardinality common
independent set, we need
to show the algorithm
finds the maximum cardinality
common independent set
and the masking set
, so that
reaches the maximality
while reaches the
minimality in the following
min-max relationship,
which is similar to the
König-Egerváry Theorem:
Assertion (Edmonds, Matroid Intersection Theorem)
This relationship generalizes
many graph theoretic min-max
relationships when appropriate
matroids are constructed,
which we will see later.
Construction of Exchange Graphs
We begin with introducing
the concept of exchange
graph, which plays the core
role in our algorithm to
find the maximum cardinality
common independent set:
Definition (Exchange Graphs)
In matroid
,
for an independent set
,
we may construct an
the exchange graph
of , which is a
simple
-bigraph
such that:
Example
For the maximal matching
in the bipartite graph
we've shown in the
beginning of this text,
the exchange graphs of it
in matroids and
are:
Example
For the maximum matching
in the bipartite graph
we've shown in the
beginning of this text,
the exchange graphs of
it in matroids
and are:
We will characterize some properties of
the exchange graph in this section.
Independent Sets and the Matchings in the Exchange Graphs
Clearly for those differs from the
current independent set by one
element, they corresponds to an
edge in the exchange graph. But
we would like to show for every
independent sets of the same
cardinality, there's a matching
corresponds to it.
To show, we will introduce the
concept of matroid restricted
to size:
Definition (Size-Restrictions of Matroids)
For any matroid ,
the size-restriction of
to size is a matroid
,
such that
.
Proof. Clearly there's
and
.
And since
,
while
,
the independent set exchange
property also holds. Therefore
is a matroid.
With it, we will be able to show:
Lemma
For any independent sets
,
if , then there's
a matching between
and
in the exchange graph
.
Proof. If ,
now consider the size-restriction
, clearly
are bases in
and thus
the (even stronger version of) strong basis exchange property
is applicable to now.
Due to the strong basis
exchange property, there's
such that
.
Since
,
an edge is to be found
in .
Meantime
is again an independent
set obtained from
by replacing with ,
such that
.
We may recursively apply
the lemma on those
independent sets differing
from by less elements,
which clearly holds when
the independent set differs
from by element.
For the matching found
between and ,
is the matching between
and .
Please notice merely the
(weaker version of) strong
basis exchange property
does not guarantee
the pair of chosen
such that
to correspond to edge in
, as long as
.
Finding Independent Sets by the Matchings in the Exchange Graphs
Given the correspondence
relationship between matchings
in the exchange graph and
the independent set of the
same cardinality, a natural
question rises as, given a
matching , does it
necessarily yield an
independent set after
performing the exchange
operations specified by ,
say for
all vertices the
edges in incident to, and
the symmetric difference
between sets?
The answer is, unfortunately, no:
Counterexample
Consider the matroid
such that:
The content of exchange graph
is
shown to the right. When we take
the matching
to fix , the resulting
is dependent.
Although not every matching
in the exchange graph
corresponds to an
independent set, we would
like to show, there's still
a way we can guarantee the
matching found in exchange
graph corresponds to an
independent set:
Assertion
If the matching in the
exchange graph
is the unique matching saturing
, then is
an independent set.
And we will see, this guarantee
suffices for our algorithm to
find the maximum cardinality
common independent set later.
Let's begin with characterizing
unique matchings:
Lemma
For an -bigraph and
a matching , we claim that
is not the unique
matching saturing iff
there's an -alternating
cycle in .
Proof. The sufficiency
is obvious, for the cycle
found in , just by
doing we
obtain another matching
saturing , so is
not unique.
For the necessity, if
is not unique due to
another matching
saturing .
Let be the subgraph
spanned by of
, and be
the subgraph spanned
by of .
Consider ,
since ,
is not
empty. And by
the theory of matchings in bipartite graphs,
since
,
every non-trivial component
in is a cycle,
and also an -alternating.
Lemma
For an -bigraph and
a matching , orient all
edges in from to ,
and all edges in
from to , so that
we obtain an orientation .
We claim that is not
the unique matching saturing
iff
contains a cycle.
Proof. We just need to
prove that contains a cycle
iff contains an
-alternating cycle.
For the sufficiency,
it's obvious that
those -alternating cycles
in are oriented
into cycles in .
For the necessity, every cycle
in must be formed by
taking one edge from and
another edge from ,
and is thus -alternating.
What's more, to complete the
cycle, the edges in
from to must start
at those may end with,
and must end with those
may start at. Thus every
edges in are incident
only to , and to be
found in .
Now let's prove our assertion:
Theorem
If the matching in the
exchange graph
is the unique matching saturing
, then is
an independent set.
Proof. Since is the
unique matching saturing ,
let's orient the edges in
from to , and
the remaining edges from
to , so that
we obtain an orientation
of .
By previous lemma,
is acyclic.
Let's perform a topological
sort of into , and
then take the subsequence of
vertices in out
of , labeling them as
.
Then for the vertices in
matched to ,
we label them as
so that
.
It won't be hard to find
.
Assume is
dependent and contains a
circuit .
We can see
is not empty if won't like
to be a subset of , while
since
while only
may contain elements from
. Let
be the one with least
subscription in
, such that
.
Consider those
,
it won't be hard to find
,
which indicates
when viewing from ,
and thus
.
Noted that
due to
,
so
.
Meantime, we can easily see
since
has been replaced with
when evaluating
, while
.
So
,
and by combining with those in
,
we get
,
and therefore
.
Now we get a contradiction:
Since is a circuit, we have
;
On the other hand, since
,
we have
.
So our presumption that
is dependent
will never be true, and we
are done with the proof.
By now, we are done with the
construction of exchange graphs,
and ready to move on to the
main theorem.
The Main Theorem
In this section, we will
build up our data structure
and algorithm to solve the
problem of maximum cardinality
common independent set, and
then prove its correctness
by showing the min-max
relationship of the Matroid
Intersection Theorem is
reached when
the algorithm halts.
Accomodation to Augmentation
Our previous section introduces
the exchange graph, which is
good for showing the exchanging
relationship between independent
sets of the same cardinality.
However, we can tweak the
exchange graph into expressing
augmentation, by constructing
another helper matroid:
Definition (Augmented Matroids)
Given a matroid ,
we may introduce a
placeholder to
and define the augmented matroid
of , such that
.
When there're multiple
matroids identified by their
subscription, we may attach
the subscription to the
placeholders to identify
them, e.g.
for matroids
.
Proof. Clearly
,
the hereditary property in
is clear,
while for any
and any , we have
,
and
,
either case implies
,
and therefore the hereditary
property is hold in
.
To show the independent set
exchange property, for any
,
if , then
can be used to augment
when , or
can be used to augment
given that
;
if , then
clearly ,
and
can be used to augment .
Now we've turned the
augmentation into exchanging
with the placeholder:
Proof. Just use
and the definition of the
exchange graph
,
both directions are obvious.
Convention (Augmented Exchange Graphs)
In this way, for convenience,
we may define the
augmented exchange graph
for .
The placeholder is added
automatically.
Example
For the maximal matching
in the bipartite graph
we've shown in the beginning
of this text, the
augmented exchange graphs
of it in
matroids and are:
In order to obtain the maximum matching
,
we just need to do
or
.
They are both unique matchings in
each augmenting exchange graph,
as we can easily see.
Example
For the maximum matching
in the bipartite graph
we've shown in the
beginning of this text,
the augmented exchange
graphs of it in
matroids and are:
Here, the fact that and
are not adjacent to any vertex
should be unsuprising, given
that the maximum matching has been
a basis in each matroid.
Finding the Augmenting Paths
We are about to put the pieces
together. First we need to define
the augmented exchange digraph:
Definition (Augmented Exchange Digraphs)
For matroid
and matroid ,
given a common independent set
,
we obtain the orientation
of
by orienting each edge from
to , and
obtain the orientation
of
by orienting each edge from
to ,
and union them to create
the augmented exchange digraph
of , which is a
-bigraph.
Obviously, by applying the definition
above, there's
.
Example
For the maximum matching
in the bipartite graph
we've shown in the
beginning of this text,
the augmented exchange
graphs of it in
matroids and are:
Example
For the maximal matching
in the bipartite graph
we've shown in the beginning
of this text, the
augmented exchange digraph
of it is:
(Some edges referred in the following
text are colored for emphasis purpose.)
It won't be hard to find / verify,
in the augmented exchange digraph
,
there's a -path
.
If we interleave the edges
in this path by their parity
(that is, the
-th
edges go to one set of odd parity,
and the
-th
edges go to another set of even
parity), we obtain
,
so that
can be recovered
into a matching in
, and
can be recovered
into a matching in
.
This sheds light on defining
the augmenting path:
Definition (Augmenting Path)
A -path found in
is said to be an
-augmenting path.
It won't be hard to find
must be in the form of:
For
.
Let's interleave the edges
by their parity, into
of odd parity, and into
of even parity. It won't be
hard to find
can be recovered into a
matching in
,
and
can be recovered into a
matching in
.
(Convince yourself by
using the figure to the right.)
In this way, if both
and can be recovered
into unique matchings in
their own exchange graphs,
then we may augment by:
So that
.
And since is replaced
with when viewing
from ,
is replaced with
when viewing from
,
the resulting common independent
set has size .
Now the problem falls on
finding the -augmenting
path which can be recovered
into unique matchings. Luckily,
we have the following lemma:
Lemma
Let the -augmenting path
be recovered into matchings
and .
If either or
is not unique matching, then
can be shorten.
Proof. Let's begin
with showing that a strictly
shorter path might be
constructed by and
non-unique matching .
Since is not unique,
there's another matching
associated with
an -alternating
cycle . Let the cycle be
using edges in when
going from
to
, and
edges in when going
from to
. So the
cycle is in the form of
,
such that
.
Without loss of generality,
let be the one with
the earliest occurence among
in , otherwise we may shift
the cycle by:
Since such a cycle
found in a bipartite
graph must be of at
least length , we may assume
.
And we may create a shorter
in the following way:
We may let
.
Here, must occur
after since it's
matched to , which
occurs after
by the presumption of
's occuring the
earliest amomg
in . We may construct
a strictly shorter path
,
given that
,
and therefore
.
To construct a strictly
shorter path with and
non-unique matching ,
noted that
,
so for any -path
, we may use the argument
above to construct a
-path ,
which is strictly shorter
than in
,
so that
is a
strictly shorter -path
than in
.
Corollary
If is a -path
found in
that cannot be shorten,
then can be recovered
into unique matchings, and therefore
.
Proof. Just the contrapositive
of the lemma above.
The Algorithm and Main Theorem
Now we are able to present the
algorithm for finding the
maximum cardinality common
independent set:
Algorithm
The input are the matroids
, and the output
is the maximum cardinality
common independent set:
- Initialize .
- Construct the exchange digraph
.
- If , then
find the shortest
-path ,
update ,
and go back to step 2.
- Otherwise it must be the case
of ,
so halt with being the
maximum cardinality common
independent set.
One should find no difficulty
understanding the motivation of
the algorithm. Clearly
,
the shortest -path
cannot be shorten, and
every iteration we augment
the current common independent
set into a strictly larger one,
until we can't augment any more.
The algorithm should halt
eventually, since
is preserved, each iteration
we obtain a strictly larger
set, and is finite.
So the biggest problem remains
unsolved now is: How do we ensure
the common independent set found
has maximum cardinality, when
the algorithm halts? Or why
should there be no obstacle to
prevent us from augmenting
anymore, before our reaching
the maximum cardinality?
To solve this problem, we need
to justify the Matroid
Intersection Theorem:
Proof. Due to hereditary
property, both and
are
independent in both and
, and thus we have:
.
Proof. Find
and
,
and apply the previous lemma on them.
Theorem (Edmonds, Matroid Intersection Theorem)
Proof. Let be the
common independent set found
when the algorithm halts. Let
all the connectivities
(e.g. )
discussed in this proof be
evaluated in the augmented
exchange digraph
.
To justify the theorem, we
need to show there's a masking
set associated with
such that
and
.
In this way, given that
,
by combining with previous
lemma, there can only be
.
We claim that
would be such a masking set.
Assume ,
then there must be
such that
,
so there must be
such that
.
Obviously there's
,
but if , then
implies , and
since
,
there must be
,
which is a contradiction to
the algorithm has halted with
.
So
it must only be the case that
.
In this way, we can use elements
in to augment
into
for some ,
so there must be
in the first place.
But is obtained from
exchanging with in ,
so , and this will imply
,
which is a contradiction.
So there can only be
.
Similarly, assume
.
So there's some
to send out to augment
, into
.
Again,
since otherwise
,
which is a contradiction.
We may augment
into
for some ,
but
,
and
,
which is a contradiciton.
So it can only be
.
Now we have justified the Matroid
Intersection Theorem, and meantime
proved the correctness of
our algorithm to find the maximum
cardinality common independent set.
On the other hand, it won't be
hard to find
can also be used as a masking set
such that
(Be cautious about which matroid
does the masking set find the
maximal independent set for!)
by applying the almost identical
argument to the proof of Matroid
Intersection Theorem above.
Due to the construction of the
masking set, we may furtherly prove:
Corollary
When the algorithm halts, let
when referring to the
augmented exchange digraph
,
then is closed in ,
and is closed in .
Proof. Recall the proof of
Matroid Intersection Theorem, in
which we've constructed the
masking set
such that
.
Noted that ,
so if we are able to show
,
then
is closed in .
In the first place, since
,
those will
surely yield
.
And for those ,
since , either
or
.
Either case implies there's some
such that
,
for when ,
or when .
So it's also the case of
.
Since ,
we have shown
,
so ,
and therefore is closed.
To prove is closed, just
noted that we may also construct
the masking set
such that
.
And since ,
we may apply the completely
identical argument to this
case, so that we have
,
and thus
is closed.
König-Egerváry Theorem from Matroid Theory
As is said, that many graph
theoretic min-max relationships
can be derived from the
Matroid Intersection Theorem,
when appropriate matroids are
constructed, let's give it
a shot with the
König-Egerváry Theorem.
We are familiar with the way
of handling matchings: Given
a -bigraph , it won't
be hard to find that we may construct
for
,
and
for
,
so that
is a matching in iff
.
When it comes to the vertex
cover, given that a vertex
cover is a subset of ,
while are
matroids over , we
need to do the following
transformations if the
Matroid Intersection Theorem
would like to be applicable:
- Given a vertex cover
such that
,
we transform it into
and
.
- Given two edge sets
, we
transform them into
,
for retrieving
all vertices that
edges in edge set
are incident to.
We will refer to them as
transformation rule 1 and
rule 2 in this section.
And it's easy to see:
Lemma
For edge sets
obtained from transforming
vertex cover , there're
,
and
.
Proof. Given that
is a vertex cover, every
edge must be incident to
a vertex in , so
.
To show is closed,
just consider what circuits
in looks like. Given
that is a partition
matroid of rank uniformly
on each summand uniform matroid,
every circuit in
must be in the form of
for .
However, if
is found in , then
and thus
.
In this way, any edge in
can not
complete a circuit with
subsets of , otherwise
such an edge is in ,
which is a contradiction.
And thus is closed.
By similar argument, we may
show to be closed.
Lemma
For edge sets
obtained from transforming
vertex cover , there's
.
Proof. For each
, the
transformation rule 1
maps it into the union
summand
of . If
is not
empty, given that
,
the uniform matroid summand
of will be at least
providing element . And
since each uniform matroid
summand has rank , every
such that
is not
empty will count for
in .
Otherwise if
is empty,
it correspond to no uniform
matroid summand, and thus
counts for in
.
In this way, we have
.
By analogous argument, we
may also show
.
Lemma
For vertex cover obtain
from recovering edge sets
such that
,
there're
.
Proof. Independent set
in is obtained from the
disjoint union of each uniform
matroid summand providing
element, so
counts the number of uniform
matroid summands providing
element. And by transformation
rule 2, vertices recovered to
are exactly the
representative vertices of
uniform matroid summands
providing elements, thus
.
By analogous argument to
we may also show
.
And among the combinations of
closed subsets in each matroids
that unions into the ground
set, we can prove Matroid
Intersection Theorem finds one
of them reaching the minimality
in the following
min-max relationship:
Proof. First, it's obvious that
,
so
.
And therefore
by choosing maximizing and
minimizing
.
The algorithm of the Matroid
Intersection Theorem finds
that is closed in
and partiions the
maximum cardinality common
independent set together
with . And
by letting
,
we have
,
and since
,
the equality is reached
by such a combination
of .
Alternatively, we may also let
for found by the
algorithm of the Matroid
Intersection Theorem.
And due to the argument
analogous to the one
above, we may show
is such a
combination reaching
the equality of the
min-max relationship.
This can be used to show:
Proof. By previous
lemma, we know the Matroid
Intersection Theorem finds
the closed sets
minimizing
,
among closed sets
of
that .
Let them be recovered into
vertex cover
by transformation rule 2,
and we know there's:
On the other hand, let
be the vertex cover minimizing
cardinality, so
.
Let be transformed
into vertex sets
by rule 1,
so
.
while:
So eventually, they combine into:
And thus
.
In this way, for the closed sets
found by the algorithm of
Matroid Intersection Theorem,
recovered from
minimizes cardinality
among vertex covers.
It's interesting to think
about which vertex cover
is found by the
Matroid Intersection Theorem.
Let
be the closed sets found,
and attemp to recover
them into vertex cover
by transformation rule 2.
Given that
,
those elements
that are connected to
are surely in ,
by extensive property.
Consider any ,
let the -path be
ending with ,
by definition is
an edge incident to a
vertex in unsatured by
. And clearly there must
be some if
won't like to form
an -augmenting path.
Again by definition,
and incident
to the same vertex in ,
which is satured by
with .
What if such the
-path can be
extended even longer? Let
there be
in the path, so
are
incident to the same
vertex in , and there
must be also
for incident to
the same vertex as
in , if
won't like to form
an -augmenting path.
If we keep on reasoning
in such a way, we will
find can be
recovered into
that are vertices in
connected to vertices
unsatured by in .
Similarly,
can be recovered
into that are
vertices in not
connected to vertices
unsatured by in .
In this way, Matroid
Intersection Theorem
implies König-Egerváry
theorem, in a sufficient
but relatively obscure way.
Matroid Union Theorem
First, let's define the
union of matroids:
Definition (Union of Matroids)
Given matroids
over ground set , the
union
of matroids
is
a hereditary system, such that
.
Proof. Clearly
.
And for any
,
we have
,
and thus
.
The simplest form of union of
matroids might be direct sum
of matroids
over
disjoint ground sets
.
By letting
as the ground set,
we may transform each summand
of the direct sum into
the summand
of
the union, so that
.
The general form of union of
matroids is complicated,
given that different matroid
summands might provide
overlapping union summands
for an independent set in
.
And we may ask the problem
analogous to the intersection
of matroids: What is the
maximum cardinality of the
independent set of union
of matroids, and how to
find such an independent set?
Interestingly, such a
problem is also convertible
to finding maximum cardinality
common independent set of
two delicately constructed
matroids, and thus the Matroid
Intersection Theorem is
applicable again. We will
show how to accomplish this
in this section.
Reduction to Matroid Intersection Problem
Let the ground set be
,
we duplicate each element in
for times, into
,
so that
are copies of .
For convenience, we may let
,
and
.
We may put them inside a matrix
so that we can interpret our
proposed configuration intuitively:
For the union of matroids
,
we may define its
row projection matroid
,
such that
by
matroid isomorphism
defined as
;
we may also define its
column projection matroid
.
Our goal is to establish
the connection between
and
.
Proof. When viewing from the
column projection matroid, every
direct sum summand
must
provide or element, so
for every
,
are pairwisely disjoint, and thus
.
When viewing from the row projection
matroid, there's obviously
.
So by letting
,
we obtain the independent set
in
such that .
Proof. For any
such that
,
we present a method of
"Gaussian elimination":
We may let
and
,
so that we obtain
that are pairwisely disjoint.
And by letting
,
we obtain an independent set
of the column projection matroid
, such that .
On the other hand, it won't be
hard to see
.
So we have
.
By now, we are done with showing
there's
corresponding to every
,
such that .
Proof. Let
be converted from
maximizing cardinality in
,
let be converted from
maximizing cardinality in
.
Obviously we have
.
In this way, we've converted
the problem of finding
maximum cardinality independent
set in the union of matroids,
into finding maximum cardinality
common independent set of
row projection matroid and
column projection matroid.
Applying the Matroid Intersection Theorem
By applying the Matroid
Intersection Theorem to the
row projection matroid and
column projection matroid,
we obtain the
Matroid Union Theorem immediately:
Theorem (Edmonds-Fulkerson, Nash-Williams, Matroid Union Theorem)
Proof. Let's begin with studying
what Matroid Intersection Theorem
finds for us when maximizing
and minimizing
.
Due to
this corollary,
is a closed set in
found by the
algorithm of Matroid
Intersection Theorem.
But being closed in
, which is a
partition matroid of
rank uniformly,
means it must contain
a whole column at a time.
For this reason, both
and must
contain the whole columns.
In this way, we may let
each and
correspond to
and
, such that
.
And it's obviously
under such a correspondence.
Now let's evaluate
. When viewing
from the rows. Each intersects
with at
, and thus
.
By substituing them into
,
we get
,
and we are done with the proof.
The Union of Matroids is Matroid
Unlike the intersection of two
matroids, which is generally
not a matroid, we would like
to show the union of matroids
is a matroid.
First, we need to extend the
restriction of matroids to
the union of matroids:
Proof. Consider the
elements in the set
.
We can see
for ,
and thus we have
.
and
.
On the other hand, consider any
we have
,
while
by
hereditary property, which implies
for .
So we also have
and thus
.
Finally, by mutual inclusion,
we have
.
Noted that
is also a union of matroids,
so the Matroid Union Theorem
is applicable, with which
we have:
Proof. Just notice that
for .
Clearly
defines the rank function
of
if it were a matroid. And
if we are able to show
defined in such a way
fulfills the axioms of
rank function on ,
then the union
is indeed a matroid due to the
rank function axioms of matroids:
Theorem
The function
defined as
fulfills the axioms of
rank function on , and
thus the union
is a matroid.
Proof. Noted that
,
let
so we have
directly.
To show the monotonicity,
for any ,
additionally consider
:
Since ,
we have .
And we also have
,
while
.
No matter which case we have
.
So we have
,
while
also fits into it.
Finally, we will show
to be submodular,
and due to
this argument
fulfills the weak
absorption rule. For
,
consider
and
,
we have
.
Given that
,
we have:
By studying the set inclusions and
operations of
,
we have:
Finally, due to the submodularity
of each rank function
of , we have:
Now function fulfills all the
axioms of rank function, defining
the rank function of
and revealing it to be a matroid.
Matroid Covering and Packing Theorem
The Matroid Union Theorem doesn't
forbid using the same matroid
as the union summand for multiple
times. Actually, we will see,
doing so will turn the Matroid
Union Theorem into a strong tool,
for studying and answering
the questions about the
structure of the unions of
independent sets.
Consider a matroid
, one
question we may ask is:
Can we cover using
independent sets, say
for
?
When the matroid contains a
loop , clearly the
answer is "nope", since
there's no independent set
to cover , and is
left as a hole.
When the matroid is loopless /
contains no loop, let
,
given that
,
at least we can cover by
,
so it's always true for
, while less
independent set might suffice.
And in general, the question
is asked for some .
Such a question can be solved
by unioning the same matroid
for times:
Theorem (Edmonds, Matroid Covering Theorem)
The ground set of a
loopless matroid
can be covered by
independent sets
iff
.
Proof. Let
,
clearly the ground set
can be covered by
independent sets iff
.
On one hand,
will imply
,
and thus
.
When , it
becomes
,
which is trivially true.
When , it
can be transformed into
. By 's
being loopless, we have
.
On the other hand, if
,
we have
.
By combining with
,
we have
.
But by combining with
,
we may only have
.
Given that
,
we have .
Corollary
A loopless matroid
over can be covered
by at least
independent sets.
Proof. Nothing more
than finding the minimum
in the previous
theorem, and then rounding
to the integers.
Another question we may ask
is: Can we pack pairwisely
disjoint bases
into , that is, is it
possible that
?
Such a question is also
solvable by unioning
for times:
Theorem (Edmonds, Matroid Packing Theorem)
It's possible to pack
pairwisely disjoint
bases into iff
.
Proof. Again, let
.
We claim that we can
pack pairwisely disjoint
bases into iff
.
First, we can show
,
since otherwise for
,
in its decomposition
of independent sets,
there must be a
independent set component
containing more than
elements, which
is a contradiction.
When pairwisely
disjoint bases is packed
into as
,
there must be .
And by combining with
,
it's only possible that
.
Conversely, if
, then
there must be
,
and can only be the
disjoint union of
bases, if no
independent set summand
of would like to
contain more than
elements.
Again, we would like to show
is equivalent to
.
When
, there's
,
and thus
.
When ,
is
trivially true for
.
And when ,
is implied.
Conversely, when
,
it can be recovered into
.
When ,
is trivially true.
So it's always
,
and thus
.
By combining with
,
it's only
.
Corollary
It's possible to pack at most
pairwisely disjoint bases into .
Proof. Nothing more
than finding the maximum
in the previous
theorem, and then rounding
to the integers.
Weighted Matroid Intersection
Finally, just like the weighted
version of bipartite matchings, we
would add a weighted version of
matroid intersection: Given a
weight function ,
find the maximum weighted common
independent set
.
Actually such a problem can be solved
by a somewhat sophiscated variant of
our algorithm to find the maximum
cardinality common independent set.
We will show this in this section.
Obviously, the common independent
set with maximum cardinality don't
have to be the one with maximum
weight: For some
,
by requiring only elements in
to non-negative weight and the
remaining to have negative weight,
the maximum cardinality common
independent set will inevitably
include some negative elements.
However, by defining:
Definition (Extreme Common Independent Set)
In the context of weighted
matroid intersection,
a common independent set
is said to be extreme iff
.
We can see the maximum weighted
common independent set is the
extreme common independent set
of its own size. So by finding
extreme common independent sets
of size from to
,
and returning the one with
maximum weight, we are sure to
find the maximum weighted common
independent set. Of course, if
the problem of finding the
extreme common independent
sets is solvable.
Characterization of the Weighted Augmented Exchange Digraph
First, we would like to show a
way of encoding weight
information to the augmented
exchange digraph
,
such that for every
-augmented path
found, we have
.
It's trivial to see / check,
this can be done by assigning
the edge weights:
We can see, actually we will
show later, that finding the
extreme common independent set
has something to do with
finding the walk of maximum
weight: for two -augmenting
path that cannot
be shorten, we should always
choose the larger one in weight.
Since for
,
we have
,
thus choosing yields the wrong
answer, as
implies is not extreme.
However, the most common way
to find the walk of the maximum
weight is to apply a shortest path
algorithm. This will require us
to assign negative weights, so
that minimizing is equivalent
to maximizing . So finally,
we define the weighted augmented
exchange digraph as below:
Definition (Weighted Augmented Exchange Digraph)
In the context of weighted
matroid intersection, the
weighted augmented exchange digraph
is the weighted digraph of
,
by assigning the edge weights:
In this way, for any -augmenting
path , it's
now.
Meantime, for any
,
there're matchings
between and in the
underlying exchange graphs
.
Let be the spanning subgraph of
formed by
orienting edges in from
to , and
edges in from
to . We can easily see there's:
Or equivalently
.
If would like to be
extreme, then for any
,
there must be
.
Actually, such a construction
can easily lead to:
Lemma
If
contains no negative
cycle, then is extreme.
Proof. For any
,
construct the spanning
subgraph as is said above.
Since is obtained from
orienting two matchings
, every
vertex has in-degree
and out-degree , thus
decomposes into
disjoint cycles
,
in which we have
.
Since
contains no negative cycle, we have
.
And thus
,
implying to be extreme.
Interestingly, we will show the
converse of this condition also
to be true, and lying it as the
foundation of our algorithm to find
extreme common independent sets.
Characterization of the Non-Common Independent Sets
What does a non-common independent
set look like, that is, what does
any set
look like? Clearly it's either
or
(or both),
and without loss of generality,
let it be the case of
.
Remember how we
characterize the independent sets in the exchange graphs.
When viewed from ,
if would like to be independent,
then there must be a matching between
and in
. So by taking
the contrapositive, we know no
matching between and
will sufficiently imply
.
On the other hand, we've
then proved
that having a matching does
not sufficiently imply an
independent set, but having a
unique matching will do. So
once again, by taking the
contrapositive, we know if
but there's a matching between
and , then
the matching is not unique.
Now let's combine the arguments
above, and consider the
augmented exchange digraph
.
When there's no matching between
and in
or , then we are
happy with it, since there's no
-augmenting path to augment
into . But when either
side has a non-unique matching,
it would be super annoying: When
finding the maximum cardinality
common independent set, we can
bypass it by taking the shortest
-path. But when it
comes to the weighted digraph,
the shortest -path
in weighted doesn't
necessarily have to be the
shortest in length, while
shortening it might end up
with incrementing .
And this is the case we are
going to delve into.
While there're still many cases when
but there's a non-unique matching
in either
or
, we
are only going to talk about
the case when is obtained
from for a
cycle found in
,
which turns out to
be sufficient for proving
the correctness of our
algorithm later:
Lemma
Let for
a cycle found in
,
if
,
then there's another cycle
covering strictly less vertices
(that is, )
than to be found in
,
such that
.
Proof. Without loss of
generality, let
,
and since the cycle
recovers into matchings
in
,
it must only be the case
that is not unique
and there's another matching
to be found in
.
Let
.
Without loss of generality,
we may assume
,
as we may always circurlarly
shift such a representation,
so that is matched
to different elements in
and .
We start by explicitly
constructing a cycle
covering strictly less
vertices than , using
almost the same operation
we've taken to
shorten an -augmenting path by a non-unique matching:
Here,
,
and we take
.
Clearly
by .
If
,
then we are happily done with
,
otherwise we should assume
in the following analysis.
Now let's construct a
digraph with
. Please
notice
will never incident to
since
has only outgoing edges
and has only
incoming edges, impossible
to occur in any cycle in
.
We create edge sets
on : every edge
in goes to ,
every edge in goes
to , every edge in
goes to and
, so that edges
incident to the same tuple
of vertices are considered
different when they are
in different edge sets.
That is, for any
, we create
the copy of it
in , and the copy
of it in ,
so that .
And we will let
to create this digraph.
Here's an example of how
we create such a digraph :
In this way, we can see
every vertices in has
incoming edges and
outgoing edges, thus
the underlying graph of
is even graph.
Just as even graph decomposes
into cycles, we can tweak
this proof
into showing
a digraph fulfilling
decomposes into directed
cycles, by arguing such
a relationship of
"in-degree = out-degree"
is preserved
after removing each
directed cycles.
Now we decompose with
the following steps:
- Remove the directed cycle
which is explictly
constructed by us from .
- Use edge as
the first edge, extend it
into a directed cycle ,
and remove from .
- Decompose the remaining
edges in into
directed cycles
.
After removing , the
edge
are removed from . And
after removing , all
edges incident to
has been removed. So in
the later decomposition,
will not pass ,
and thus
.
On the other hand, there
must be at least one
cycle found at step 3,
that is, :
The directed cycle
does not pass
, and as
a cycle may only pass
once. So after
step 2 there're still
one incoming edge and
one outgoing edge
incident to ,
leaving them to be
found in directed
cycle decomposed by
step 3.
Now let's analyze the
weight of the cycles.
In the first place,
we have:
By analyzing the
incoming edge incident
to each vertex. And
by presumption,
, thus:
We don't know whether it's
or
but we can analyze them
case by case. When
,
is also a cycle
covering strictly less
vertices than . When
, again
by analyzing the incoming
edge of each vertex, we have
. Thus
we have:
The first case implies there
must be a directed cycle
fulfilling ;
the second case implies there
must be a directed cycle
fulfilling
when , or
when
. And by letting
for found
in each case, we are done
with the proof.
With it, we are able to show:
Theorem
If is extreme, then
contains no negative cycle.
Proof. Assume is
extreme but
contains a negative cycle. Then
there must be a directed cycle
such that found
in the weighted digraph. Let
be the one minimizing
among these cycles.
Consider ,
since ,
we have
,
thus it must be the case of
.
By our previous lemma, we are
able to construct a cycle
covering strictly less
vertices than , but this
is a contradiction to the
minimality of .
In this way, when is extreme,
must contain no negative cycle.
Corollary
The set is extreme iff
contains no negative cycle.
This reveals the deep
connection between the extreme
common independent set and
the weighted augmented
exchange digraph without
negative cycle. Meantime,
this enable the shortest
path algorithm to find the
shortest path correctly.
The Algorithm
Finally, we would like to
present the feasibility to
find augment an extreme
common independent set
into a larger one:
Lemma
In the context of
this lemma,
for any vertex
,
if
contains
no negative
cycle, then we are able to
find the cycle
covering
strictly less vertices than
, such that
.
Proof. This involves
adding extra constraints to
our operations, when finding
cycle and decomposing
into .
First, we will show it's
possible to fix the process
of finding so that
. If
,
then .
For convenience, let
for some ,
or
for some .
Clearly defines a
permutation
so that
.
Let's track down the cycle
of containing
. Let the order of
be , so that
.
We claim that there must be some
such that
or
This can be easily shown by
considering the intersection
between segments of (straight) lines
on vertices
and the horizontal line .
Given that the segments of
straight lines is continuous
curve within interval ,
the segment from to
has already intersected
with , and the
curve must return to ,
there must be another segment from
to
intersecting with once again.
For convenience, let
.
We can pivot the cycle so that
lies in the -region now:
(Please notice the relative position
between and
doesn't have to be in the configuration
shown in the figure above. Only
is guaranteed.)
In this way, we may always ensure
to be fulfilled
unconditionally. The decomposition
of later should be based on
such a cycle found.
To prove in the
decomposition ,
we utilize the property of
's
containing no negative cycle.
In this way, it's impossible
for , since
this case implies a negative
cycle to be found. So it's
only the case
and
.
In fact, if there were any
,
then after subtracting
from both sides, we have
,
which indicates a negative cycle
to be found in
.
In this way, every cycle in
,
must fulfill
,
and we use the directed cycle
such that as .
Theorem
In the context of weighted
matroid intersection, if
is an extreme common
independent set, and
is the
shortest -path found in
,
such that for any
-walk ,
it's either ,
or ,
then
is also an extreme common
independent set.
Proof. First, we
augment both
by a common
placeholder , into
augmented matroids
over the same
ground set
(Here, we use
instead of ,
to avoid obfuscation and
confusion with the augmented
matroids that we are building
on). Clearly there's
.
Consider the augmented
exchange digraph
,
we obviously can see
and
.
In this way, for any
-path
found in
,
we can fix it into a cycle
in
passing , and vice versa.
Now we adapt by assigning
. In this
way, we can see
contains no negative cycle:
Since
contains no negative cycle and
is obtained from adding vertex to
,
if there's a negative cycle found in
,
it must pass , and such a
negative cycle
must be recovered into a -path
in
,
so that .
And
implies is an even shorter
-path than in
weight, which is a contradiction.
In this way, is
extreme in
,
let be the cycle passing
that is fixed into and
,
then obviously
.
Assume
,
then by
this lemma,
we know there's a directed cycle
covering strictly less vertices
than such that
.
Since
contains no negative cycle, the
former case has been impossible.
And for the latter case, by
the previous lemma, we know
there's a cycle
containing to be found,
which recovers into
a -path
in ,
However, we know
,
and thus
.
While
is a contradiction to 's
minimizing length among all
-walks
such that .
In this way, we are done
with showing
.
Meantime, consider any common independent set
such that ,
clearly there must also be
.
Let's construct the spanning subgraph
using the matchings between
and
in ,
by the instructions of
this argument.
Since
contains no negative cycle,
.
And since
,
there must be ,
which implies to be extreme.
This will lead us to the eventual algorithm:
Algorithm
The input are the matroids
and weight function
. The output
is the maximum weighted
common independent set:
- Initialize
.
- Construct the weighted
augmented exchange digraph
.
- If , then
find the shortest
-path ,
such that for any -walk ,
it's either
or ,
update
,
increment ,
and go back to step 2.
- Return the one with
maximum weight among
.
Clearly is
the extreme common independent
set used to ignite the process.
Each iteration we find an extreme
independent set from
. When
, there's
no larger common independent set
to be found, due to the Matroid
Intersection Theorem. So at
this point, it's time to aggregate
the result by finding the one
maximizing weight among extreme
common independent sets
extreme common independent set
we've
found so far, and halt.
To find the shortest -path
required by step 3, the Bellman-Ford
SSSP algorithm suffices, which
works in weighted digraphs
possibly with negative edge
weights but without
negative cycles.