程序代写代做代考 C algorithm graph COMP251: Bipartite graphs

COMP251: Bipartite graphs
Jérôme Waldispühl School of Computer Science
McGill University
Based on slides fom M. Langer (McGill) & P. Beame (UofW) & K. Wayne (Princeton)

Bipartite graphs
A
B
Vertices are partitioned into 2 sets. All edges cross the sets.

Examples AB
Courses Candidates People
registration employment
Have read/seen
Students Companies Books/Movies

Counter-examples
Easy to identify.
But not always…

Cycles
Claim: If a graph is bipartite if and only if does not contain an odd cycle.
Proof: Exercise.

Is it a bipartite graph?
Assuming G=(V,E) is an undirected connected graph. 1. Run DFS and use it to build a DFS tree.
2. Color vertices by layers (e.g. red & black)
3. If all non-tree edges join vertices of different color,
then the graph is bipartite.
Non-tree edges in DFS tree cross 2 or more levels. Why?

Bipartite matching
Consider an undirected bipartite graph.
AB
A matching is a subset of the edges { (α, β) } such that no two edges share a vertex.
AB

Perfect matching
A
B
Suppose we have a bipartite graph with n vertices in each A and B. A perfect matching is a matching that has n edges.
Note: It is not always possible to find a perfect matching.

Complete bipartite graph
AB
A complete bipartite graph is a bipartite graph that has an edge for every pair of vertices (α, β) such that α∈A, β∈B.

The algorithm of happiness

Resident matching program
• Goal: Given a set of preferences among hospitals and medical school students, design a self-reinforcing admissions process.
• Unstable pair: applicant x and hospital y are unstable if: o x prefers y to their assigned hospital.
o y prefers x to one of its admitted students.
• Stable assignment: Assignment with no unstable pairs.
o Natural and desirable condition.
o Individual self-interest will prevent any applicant/hospital deal from being made.

Stable matching problem
Goal: Given n elements of A and n elements of B, find a “suitable” matching. Participants rate members of opposite set:
• Each element of A lists elements of B in order of preference from best to worst.
• Each element of B lists elements of A in order of preference from best to worst.
A’s preferences B’s preferences
Xavier
Yulia
Zoran
1st
Alphabet
Baidu
Alphabet
2nd
Baidu
Alphabet
Baidu
3rd
Campbell
Campbell
Campbell
Alphabet
Baidu
Campbell
1st
Yulia
Xavier
Xavier
2nd
Xavier
Yulia
Yulia
3rd
Zoran
Zoran
Zoran

Stable matching problem
• Context: Candidates apply to companies.
• Perfect matching: everyone is matched with a single company. o Each candidate gets exactly one company.
o Each company gets exactly one candidate.
• Stability: no incentive for some pair of participants to undermine assignment by joint action.
o In matching M, an unmatched pair 𝛂-𝛃 is unstable if candidate 𝛂 and company 𝛃 prefer each other to current match.
o Unstable pair 𝛂-𝛃 could each improve by “escaping”.
• Stable matching: perfect matching with no unstable pairs.
• Stable matching problem: Given the preference lists of n candidates and n companies, find a stable matching (if one exists).

Example
Q: Is X-C, Y-B, Z-A a good assignment?
XA
Candidates Y B Companies
ZC
Candidates’ preferences Companies’ preferences
Xavier
Yulia
Zoran
1st
Alphabet
Baidu
Alphabet
2nd
Baidu
Alphabet
Baidu
3rd
Campbell
Campbell
Campbell
Alphabet
1st
Yulia
2nd
Xavier
3rd
Zoran
Baidu
Xavier
Yulia
Zoran
Campbell
Xavier
Yulia
Zoran

Candidates
Example
Q: Is X-C, Y-B, Z-A a good assignment? A: No! Xavier and Baidu will hook up…
XA
Y B Companies
ZC
Candidates’ preferences Companies’ preferences
Yulia
Zoran
1st
Alphabet
Baidu
Alphabet
2nd
Alphabet
Baidu
3rd
Xavier
Baidu
Campbell
Campbell
Campbell
Alphabet
1st
Yulia
2nd
Xavier
3rd
Zoran
Baidu
Xavier
Yulia
Zoran
Campbell
Xavier
Yulia
Zoran

Candidates
Example
Q: Is X-A, Y-B, Z-C a good assignment? A: Yes!
XA
Y B Companies
ZC
Candidates’ preferences Companies’ preferences
Xavier
Yulia
Zoran
1st
Alphabet
Baidu
Alphabet
2nd
Baidu
Alphabet
Baidu
3rd
Campbell
Campbell
Campbell
Alphabet
Baidu
Campbell
1st
Yulia
Xavier
Xavier
2nd
Xavier
Yulia
Yulia
3rd
Zoran
Zoran
Zoran

Stable matching problem
Consider a complete bipartite graph such that |A|=|B|=n.
• Each member of A has a preference ordering of members of B.
• Each member of B has a preference ordering of members of A.
Algorithm for finding a matching:
• Each A member offer to a B, in preference order.
• Each B member accepts the first offer from an A, but then
rejects that offer if/when it receives a offer from a A that it prefers more.
In our example: Candidates applies to companies. Companies accept the first offer they receive, but companies will drop their applicant when/if a preferred candidate applies after.
Note the asymmetry between A and B.

Gale-Shapley algorithm
For each α∈A, let pref[α] be the ordering of its preferences in B For each β∈B, let pref[β] be the ordering of its preferences in A Let matching be a set of crossing edges between A and B
matching¬Æ
while there is α∈A not yet matched do
β¬pref[α].removeFirst() if β not yet matched then
matching¬matchingÈ{(α,β)} else
γ¬β’s current match
if β prefers α over γ then
matching¬matching-{(γ,β)}È{(α,β)} return matching

Example
XA
Candidates Y B Companies
Z
C
Candidates’ preferences Companies’ preferences
Xavier
Yulia
Zoran
1st
Baidu
Baidu
Alphabet
2nd
Alphabet
Campbell
Campbell
3rd
Campbell
Alphabet
Baidu
Alphabet
Baidu
Campbell
1st
Zoran
Yulia
Xavier
2nd
Xavier
Zoran
Yulia
3rd
Yulia
Xavier
Zoran
Note: In practice, we inverse the roles. Companies makes offers…

Example
XA
Candidates Y B Companies
Z
C
Candidates’ preferences Companies’ preferences
Xavier
1st
Baidu
2nd
Alphabet
3rd
Campbell
Yulia
Zoran
Baidu
Alphabet
Campbell
Campbell
Alphabet
Baidu
Alphabet
1st
Zoran
2nd
Xavier
3rd
Yulia
Baidu
Campbell
Yulia
Xavier
Zoran
Yulia
Xavier
Zoran

Example
XA Candidates Y B
Companies
Z
Candidates’ preferences
C
Companies’ preferences
1st
2nd
3rd
Xavier
Baidu
Alphabet
Campbell
Yulia
Zoran
Baidu
Alphabet
Campbell
Campbell
Alphabet
Baidu
Alphabet
1st
Zoran
2nd
Xavier
3rd
Yulia
Baidu
Campbell
Yulia
Xavier
Zoran
Yulia
Xavier
Zoran

Example
XA Candidates Y B
Companies
Z
Candidates’ preferences
C
Companies’ preferences
1st
2nd
3rd
Xavier
Baidu
Alphabet
Campbell
Yulia
Baidu
Campbell
Alphabet
Zoran
Alphabet
Campbell
Baidu
1st
2nd
3rd
Alphabet
Zoran
Xavier
Yulia
Baidu
Campbell
Yulia
Xavier
Zoran
Yulia
Xavier
Zoran

Candidates
Example
XA
Y B Companies
Z
C
Men’s preferences Companies’ preferences
Xavier
Yulia
Zoran
1st
Baidu
Baidu
Alphabet
2nd
Alphabet
Campbell
Campbell
3rd
Campbell
Alphabet
Baidu
Alphabet
Baidu
Campbell
1st
Zoran
Yulia
Xavier
2nd
Xavier
Zoran
Yulia
3rd
Yulia
Xavier
Zoran

Correctness (termination)
Observations:
1. Candidates apply to companies in decreasing order of preference.
2. Once a company is matched, it never becomes unmatched; it only “trades up.”
Claim: Algorithm terminates after at most n2 iterations of while loop (i.e. O(n2) running time).
Proof: Each time through the while loop a candidate applies to a new company. There are only n2 possible matches.n

Correctness (perfection) Claim: All candidates and companies get matched.
Proof: (by contradiction)
• Suppose, for sake of contradiction, that Zoran is not matched
upon termination of algorithm.
• Then some company, say Alphabet, is not matched upon termination.
• By Observation 2 (only trading up, never becoming unmatched), Alphabet never received any application.
• But, Zoran applies everywhere. Contradiction.n

Correctness (stability) Claim: No unstable pairs.
Proof: (by contradiction)
• Suppose Z-A is an unstable pair: they prefer each other to the
association made in Gale-Shapley matching.
• Case 1: Z never applied to A. ⇒ Z prefers his GS match to A. ⇒ Z-A is stable.
• Case 2: Z applied to A.
⇒ A rejected Z (right away or later)
⇒ A prefers its GS match to Z.
⇒ Z-A is stable.
• In either case Z-A is stable. Contradiction.n

Optimality
Definition: Candidate 𝛂 is a valid partner of company 𝛃 if
there exists some stable matching in which they are matched.
Applicant-optimal assignment: Each candidate receives best valid match (according to his preferences).
Claim: All executions of GS yield an applicant-optimal assignment, which is a stable matching!
Note: the notation “Applicant-optimal” refers to 𝜶-optimality

Example
X
Y
Z
1st
B
A
A
2nd
A
B
B
3rd
C
C
C
A
B
C
1st
X
Y
X
2nd
Y
X
Y
3rd
Z
Z
Z
Two stable matchings: S = { X-A, Y-B, Z-C } and Sʹ = { Y-A, X-B, Z-C }
Then:
• BothXandYarevalidpartnersforA.
• BothXandYarevalidpartnersforB.
• ZistheonlyvalidpartnerforC.
• InS’,XYZmatchtheirbestvalidpartner.

Applicant-Optimality Claim: GS matching S* is applicant-optimal.
Proof: (by contradiction)
• Suppose some candidate is paired with a company other than his/her best
option. Candidates apply in decreasing order of preference ⇒ some
candidate is rejected by a valid match.
• Let Y be first such candidate, and let A be the first valid company that
rejects him (i.e. Y-A is optimal).
• Let S be a stable matching (not from GS) where Y and A are matched.
• [In GS] when Y is rejected, A forms (or reaffirms) engagement with a
candidate, say Z, whom it prefers to Y ⟹ A prefers Z to Y.
• LetBbeZ’smatchinS.
• [In GS] Z is not rejected by any valid match (including B) at the point when
Y is rejected by A (because Y is the first valid rejection). Thus, Z has not
proposed to B when Z proposed to A ⟹ Z prefers A to B.
• Thus A-Z would be preferred in GS (i.e. Y-A and Z-B are unstable) and S is
not a stable matching. Contradiction.n

Why does Z prefer A to B?
In Gale-Shapley S
YAYA ZBZB
• Y is the first rejection of a valid pair.
• Y-A rejected because of Z
⟹ if Z had proposed to B before it would need to break the valid pair Z-B first
⟹ impossible (Y first reject) ⟹ Z did not proposed to B
S is a stable matching
⟹ Y-A and Z-B are valid pairs

Company(𝛽)-pessimality
Each element of (𝛽) receive the worst valid partner
Claim: GS find the finds a student-pessimal stable matching. Proof: Exercise… (by contradiction)

Related Posts