Matchings in Graphs Variations of the Problem

Many real-life optimization problems are naturally formulated as questions about matchings in (bipartite) graphs.

We have a bipartite graph. The edge set is partitioned into classes

E

1

,

E

2

, . . . ,

E

r

. For a matching

M

, let

s

i

be the number of edges in

M

 ∩ 

E

i

. A

rank

 − 

maximal

matching maximizes the vector (

s

1

,

s

2

, . . . ,

s

r

). We show how to compute a rank-maximal matching in time O(r

$\sqrt{nm}$

) [IKM

 + 

06].

We have a bipartite graph. The vertices on one side of the graph rank the vertices on the other side; there are no ties. We call a matching

M

more popular than a matching

N

if the number of nodes preferring

M

over

N

is larger than the number of nodes preferring

N

over

M

. We call a matching popular, if there is no matching which is more popular. We characterize the instances with a popular matching, decide the existence of a popular matching, and compute a popular matching (if one exists) in time O(

$\sqrt{nm}$

) [AIKM05].

We have a bipartite graph. The vertices on both sides rank the edges incident to them with ties allowed. A matching

M

is

stable

if there is no pair

$(a, b) \in E{\backslash}M$

such that

a

prefers

b

over her mate in

M

and

b

prefers

a

over his mate in

M

or is indifferent between

a

and his mate. We show how to compute stable matchings in time

O

(

nm

) [KMMP04].

In a random graph, edges are present with probability p independent of other edges. We show that for p ≥

c

0

/n and

c

0

a suitable constant, every non-maximal matching has a logarithmic length augmenting path. As a consequence the average running time of matching algorithms on random graphs is O(m log n) [BMSH05].