Textbook

Chapter 1

Adjacency

Two vertices $x$ and $y$ within graph $G=(V,E)$ are considered adjacent if they share an edge between them. That is,

$$ \exists e \in E \mid e(x,y) $$

Disjoint Sets

Two sets $M$ and $N$ are disjoint if no member of $N$ is also member of $M$, and vice versa. That is,

$$ \forall m \forall n ((m \in M \implies m \notin N) \land (n \in N \implies n \notin M)) $$

By definition, the intersection of the two sets $M \cap N$ is the empty set $\varnothing$.

Independent Sets

Given a graph $G=(V,E)$, a set of vertices $S$ within $G$, is independent if no two vertices $x$ and $y$ within $S$ are adjacent to one another. That is,

$$ S \subseteq V \land \forall x \forall y (x \in S \land y \in S \land \nexists e_{(x,y)} \in E) $$

Bipartite Graphs

Matching

Given a graph $G=(V,E)$, a matching $M$ is a set of pairwise non-adjacent edges within that graph. That is, a set of edges between vertices in which no two edges share the same vertex. Equivalently, a matching can be considered to be a bijection between a subset of the vertices within a graph.

Bipartite Matching

A bipartite matching $M$ consists of two sets of vertices $U$ and $V$ that are disjoint and independent.

1. $\exists U \exists V \mid U \cap V = \varnothing$

2. $\forall u \in U \ \exists v \in V \mid e_{(u,v)} \in E$

3. $\forall v \in V \ \exists u \in U \mid e_{(u,v)} \in E$

Perfect Matching

A matching $M$ is perfect if it is a matching of a graph $G=(V,E)$ such the edges in $M$ are collectively incident to every vertex within $V$.

Stable Matching

Given a complete bipartite graph $G=(U,V,E)$, let $u$ represent a vertex within $U$, and let $v$ represent a vertex within $V$. A matching $M$ within $G$ is considered stable if there is no pair of vertices $u$ and $v$ who both mutually prefer one another over their current partner in $M$.

To find a stable matching, use the Gale Shapley algorithm, which is guaranteed to find a matching that is both stable and perfect for a complete bipartite graph between two equally-sized sets of men and women.

Gale Shapley Algorithm:

While there is still a man M who is single:
    
    Go through the list of woman
    ...in descending order of preference
    ...excluding women he has previously propesed to
    ...and choose the one he prefers most

    Propose, regardless of her current engagement status
    (She is guaranteed to accept, provided that she 
    prefers this man over her current fiance)

    If she says no, the man remains single
    If she says yes, her fiance becomes single

Time Complexity: $O(n^2)$ where $n$ is the number of vertices in each partition. Space Complexity: $O(n^2)$

The Gale Shapley algorithm ensures that the men (the gender that proposes) are guaranteed to end up with their highest rated choice, regardless of the order in which a particular man proposed, after taking into account the women's preference (or dispreference) for a particular man.

The Gale Shapley algorithm will produce the same stable matching regardless of the order in which the men propose.

Chapter 1.2

The interval scheduling problem is solved with the greedy algorithm "always choose the earliest non-overlapping interval available"

The weighted interval scheduling problem requires dynamic programming in order to arrive at an optimal solution.

The bipartite matching problem is to find the bipartite matching in a graph with the greatest number of vertices.

Given a graph $G=(V,E)$, we say a set of nodes $S \subseteq V$ is independent if no two nodes in $S$ are joined by an edge.

The independent set problem is to find the independent set in a graph with the greatest number of vertices. This problem is $NP$-complete

The competitive facility location problem is a bit complicated to encapsulate in a note.

Chapter 1 Solved Problem 1

Consider a town with n men and n women seeking to get married to one another. Each man has a preference list that ranks all the women, and each woman has a preference list that ranks all the men.

The set of all 2n people is divided into two categories: good people and bad people. Suppose that for some number k, 1 ≤ k ≤ n − 1, there are k good men and k good women; thus there are n − k bad men and n − k bad women.

Everyone would rather marry any good person than any bad person. Formally, each preference list has the property that it ranks each good person of the opposite gender higher than each bad person of the opposite gender: its first k entries are the good people (of the opposite gender) in some order, and its next n − k are the bad people (of the opposite gender) in some order.

Show that in every stable matching, every good man is married to a good woman.

Chapter 1 Solved Problem 2

We can think about a generalization of the Stable Matching Problem in which certain man-woman pairs are explicitly forbidden. In the case of employers and applicants, we could imagine that certain applicants simply lack the necessary qualifications or certifications, and so they cannot be employed at certain companies, however desirable they may seem. Using the analogy to marriage between men and women, we have

• A set $M$ of $n$ men
• A set $W$ of $n$ women
• A set $F \subseteq M \times W$ of pairs who are simply not allowed to get married

Each man $m$ ranks all the women $w$ for which $(m, w) \in F$

Each woman $w'$ ranks all the men $m'$ for which $(m', w') \in F$

In this more general setting, we say that a matching S is stable if it does not exhibit any of the following types of instability.

1. There are two pairs $(m,w)$ and $(m',w')$ in $S$ with the property that $(m,w') \in F$, $m$ prefers $w'$ to $w$, and $w'$ prefers $m$ to $m'$. This represents the prototypical instance of an instability.

2. There is a pair $(m,w) \in S$, and a man $m'$, so that $m'$ is not part of any pair in the matching, $(m',w) \in F$ , and $w$ prefers $m'$ to $m$. This is the case in which a single man is more desirable and not forbidden.

3. There is a pair $(m,w) \in S$, and a woman $w'$, so that $w'$ is not part of any pair in the matching, $(m,w') \in F$, and $m$ prefers $w'$ to $w$. This is the case in which a single woman is more desirable and not forbidden.

4. There is a man $m$ and a woman $w$, neither of whom is part of any pair in the matching, so that $(m,w) \in F$. This is the case in which there are two single people with nothing preventing them from getting married to each other.

Note that under these more general definitions, a stable matching need not be a perfect matching.

Now we can ask: For every set of preference lists and every set of forbidden pairs, is there always a stable matching? Resolve this question by doing one of the following two things:

1. Give an algorithm that, for any set of preference lists and forbidden pairs, produces a stable matching
2. Give an example of a set of preference lists and forbidden pairs for which there is no stable matching.

Docs just now