Advanced Algorithms End Term: 22 December 2024 (September 2024 term)

In this world, there are only two kinds of people: people who love Hanumankind, and people who do not love Hanumankind.

We are searching for a stable matching for everyone. The situation is as follows:

• For some $n \geq 5$, there are $n$ men, $n$ women, and one Hanumankind. We also use $k$ to denote $n - 5$.
• Men and women can be matched to each other as usual.
• Anyone can be matched with Hanumankind.
• Everyone is either Skeptic or a Believer. Skeptics want to be matched with anyone except Hanumankind. Believers really want to be matched with Hanumankind but don't mind being matched with other people.
• Men and women still have preference lists, as usual, but if they are a Believer, Hanumankind is always in the first position. If they are Skeptic, Hanumankind is always in the last position.
• Hanumankind desires to match with 10 people — to be known as the Believers Club — to party forever. As Hanumankind is a kind person and wishes to be inclusive, the goal Believers Club will have exactly 5 men and 5 women.
• Hanumankind also has a preference list containing all $2n$ men and women.

A stable matching is defined as follows:

• Hanumankind has 10 partners, of which 5 are men and 5 are women.
• All men and women not matched up with Hanumankind are married to someone of the opposite gender.
• No unstable couples exist; i.e., there is no man M and woman W such that M prefers W to his current wife, and W prefers M to her current husband.
• No skeptic is matched with Hanumankind, i.e, the Believer's Club only admits Believers.
• There is no man who (1) is not matched with Hanumankind; and (2) who is preferred by Hanumankind over one of his current male partners; and (3) who prefers Hanumankind over his matched partner.
• There is no woman who (1) is not matched with Hanumankind; and (2) who is preferred by Hanumankind over one of his current female partners; and (3) who prefers Hanumankind over her matched partner.

Based on the above data, answer the given subquestions.

What is a necessary condition for the existence of a stable matching? A condition is a necessary condition if, when it does not hold, a stable matching cannot exist. Check all that apply.

In this world, there are only two kinds of people: people who love Hanumankind, and people who do not love Hanumankind.

We are searching for a stable matching for everyone. The situation is as follows:

• For some $n \geq 5$, there are $n$ men, $n$ women, and one Hanumankind. We also use $k$ to denote $n - 5$.
• Men and women can be matched to each other as usual.
• Anyone can be matched with Hanumankind.
• Everyone is either Skeptic or a Believer. Skeptics want to be matched with anyone except Hanumankind. Believers really want to be matched with Hanumankind but don't mind being matched with other people.
• Men and women still have preference lists, as usual, but if they are a Believer, Hanumankind is always in the first position. If they are Skeptic, Hanumankind is always in the last position.
• Hanumankind desires to match with 10 people — to be known as the Believers Club — to party forever. As Hanumankind is a kind person and wishes to be inclusive, the goal Believers Club will have exactly 5 men and 5 women.
• Hanumankind also has a preference list containing all $2n$ men and women.

A stable matching is defined as follows:

• Hanumankind has 10 partners, of which 5 are men and 5 are women.
• All men and women not matched up with Hanumankind are married to someone of the opposite gender.
• No unstable couples exist; i.e., there is no man M and woman W such that M prefers W to his current wife, and W prefers M to her current husband.
• No skeptic is matched with Hanumankind, i.e, the Believer's Club only admits Believers.
• There is no man who (1) is not matched with Hanumankind; and (2) who is preferred by Hanumankind over one of his current male partners; and (3) who prefers Hanumankind over his matched partner.
• There is no woman who (1) is not matched with Hanumankind; and (2) who is preferred by Hanumankind over one of his current female partners; and (3) who prefers Hanumankind over her matched partner.

Based on the above data, answer the given subquestions.

What is a sufficient condition for the existence of a stable matching? A condition is a sufficient condition if, when it holds, a stable matching is guaranteed to exist. Check all that apply.

In this world, there are only two kinds of people: people who love Hanumankind, and people who do not love Hanumankind.

We are searching for a stable matching for everyone. The situation is as follows:

• For some $n \geq 5$, there are $n$ men, $n$ women, and one Hanumankind. We also use $k$ to denote $n - 5$.
• Men and women can be matched to each other as usual.
• Anyone can be matched with Hanumankind.
• Everyone is either Skeptic or a Believer. Skeptics want to be matched with anyone except Hanumankind. Believers really want to be matched with Hanumankind but don't mind being matched with other people.
• Men and women still have preference lists, as usual, but if they are a Believer, Hanumankind is always in the first position. If they are Skeptic, Hanumankind is always in the last position.
• Hanumankind desires to match with 10 people — to be known as the Believers Club — to party forever. As Hanumankind is a kind person and wishes to be inclusive, the goal Believers Club will have exactly 5 men and 5 women.
• Hanumankind also has a preference list containing all $2n$ men and women.

A stable matching is defined as follows:

• Hanumankind has 10 partners, of which 5 are men and 5 are women.
• All men and women not matched up with Hanumankind are married to someone of the opposite gender.
• No unstable couples exist; i.e., there is no man M and woman W such that M prefers W to his current wife, and W prefers M to her current husband.
• No skeptic is matched with Hanumankind, i.e, the Believer's Club only admits Believers.
• There is no man who (1) is not matched with Hanumankind; and (2) who is preferred by Hanumankind over one of his current male partners; and (3) who prefers Hanumankind over his matched partner.
• There is no woman who (1) is not matched with Hanumankind; and (2) who is preferred by Hanumankind over one of his current female partners; and (3) who prefers Hanumankind over her matched partner.

Based on the above data, answer the given subquestions.

Consider the algorithms below:

Algorithm A. If there are fewer than 5 male believers or fewer than 5 female believers, stop and conclude that there is no stable matching. Otherwise, take Hanumankind's 5 favorite male Believers and his 5 favorite female Believers, and include them in the Believer's club.

Remove Hanumankind and the club from all remaining preference lists, and run the Gale-Shapley algorithm on everyone else ($k$ men and $k$ women).

Return this matching.

Algorithm B. Take Hanumankind's top 5 male preferences and top 5 female preferences, and include them in the Believer's club. Remove Hanumankind and the club from all remaining preference lists, and run the propose and reject algorithm on everyone else ($k$ men and $k$ women).

Return this matching.

Algorithm C. In this algorithm, we will try to leverage the original Gale-Shapley algorithm on the entire instance by artificially making 5 male and 5 female “copies” of Hanumankind, and their matched partners will ultimately form the Believer's club. We do this as follows:
\

• Introduce 5 new male and 5 new female entities to the world, say $M_1, \ldots, M_5$ and $W_1, \ldots, W_5$.\
• Let $W^\star$ be Hanumankind's preference list projected on the $n$ women, followed by $W_1, \ldots, W_5$.\
• Let $M^\star$ be Hanumankind's preference list projected on the $n$ men, followed by $M_1, \ldots, M_5$.\
• The preference list of $M_i$ is $W^\star$ for all $1 \leqslant i \leqslant 5$.\
• The preference list of $W_i$ is $M^\star$ for all $1 \leqslant i \leqslant 5$.\
• For all the male Skeptics, replace the Hanumankind entry at the bottom of the list with $W_1, \ldots W_5$.\
• For all the female Skeptics, replace the Hanumankind entry at the bottom of the list with $M_1, \ldots M_5$.\
• For all the male Believers, replace the Hanumankind entry at the top of the list with $W_1, \ldots W_5$.\
• For all the female Believers, replace the Hanumankind entry at the top of the list with $M_1, \ldots M_5$.
  
  Now run the Gale-Shapley algorithm on this instance with $n + 5$ men and $n + 5$ women.
  
  Take everyone matched with $M_1, \ldots, M_5$ and $W_1, \ldots, W_5$ and include them in the Believer's Club, and keep the rest of the matching as-is.
  
  Return this matching.

Which of the algorithms above is correct?

In this world, there are only two kinds of people: people who love Hanumankind, and people who do not love Hanumankind.

We are searching for a stable matching for everyone. The situation is as follows:

• For some $n \geq 5$, there are $n$ men, $n$ women, and one Hanumankind. We also use $k$ to denote $n - 5$.
• Men and women can be matched to each other as usual.
• Anyone can be matched with Hanumankind.
• Everyone is either Skeptic or a Believer. Skeptics want to be matched with anyone except Hanumankind. Believers really want to be matched with Hanumankind but don't mind being matched with other people.
• Men and women still have preference lists, as usual, but if they are a Believer, Hanumankind is always in the first position. If they are Skeptic, Hanumankind is always in the last position.
• Hanumankind desires to match with 10 people — to be known as the Believers Club — to party forever. As Hanumankind is a kind person and wishes to be inclusive, the goal Believers Club will have exactly 5 men and 5 women.
• Hanumankind also has a preference list containing all $2n$ men and women.

A stable matching is defined as follows:

• Hanumankind has 10 partners, of which 5 are men and 5 are women.
• All men and women not matched up with Hanumankind are married to someone of the opposite gender.
• No unstable couples exist; i.e., there is no man M and woman W such that M prefers W to his current wife, and W prefers M to her current husband.
• No skeptic is matched with Hanumankind, i.e, the Believer's Club only admits Believers.
• There is no man who (1) is not matched with Hanumankind; and (2) who is preferred by Hanumankind over one of his current male partners; and (3) who prefers Hanumankind over his matched partner.
• There is no woman who (1) is not matched with Hanumankind; and (2) who is preferred by Hanumankind over one of his current female partners; and (3) who prefers Hanumankind over her matched partner.

Based on the above data, answer the given subquestions.

Answer the given subquestions about matroids.

Answer the given subquestions about matroids.

Answer the given subquestions about matroids.

Choose the correct options:

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Consider the given statements and answer the subquestions if they are true or false.

The worst-case running time and expected running time are equal to within constant factors for any randomized algorithm.

Consider the given statements and answer the subquestions if they are true or false.

Recall the max-flow problem: for a directed graph $G(V, E)$ with non-negative capacities $c_e$ for every $e \in E$ and two special vertices $s$ (source, with no incoming edges) and $t$ (sink, with no outgoing edges), a flow in $G$ is an assignment $f : E \to \mathbb{R}_{\geq 0}$ such that $f_e \leq c_e$ for every edge and for every vertex $v \in V, \sum_{(u,v) \in E} f((u, v)) = \sum_{(v,u) \in E} f((v, u))$. The task is to find a maximum flow $f$ i.e., a flow $f$ such that $\sum_{(s,u) \in E} f((s, u))$ is maximized.

Given an instance $(G; s, t, c)$, we attempt here to design a LP whose optimal value is equal to the maximum flow in the graph $G$. There is a variable $x_{uv}$ for all $(u, v) \in E$. Note that for any pair of vertices that is not an edge, we do not introduce any variable corresponding to it.

$\begin{aligned} &\max \sum_{u} x_{ut} \\ &\forall e = (u, v) \in E, x_{uv} \leqslant c_e \\ &\forall v \notin \{s, t\}, \sum_{u} x_{uv} = \sum_{w} x_{vw} \\ &\forall e = (u, v) \in E, x_{uv} \geqslant 0 \end{aligned}$

Is the LP above a valid formulation for computing the maximum flow in $G$?

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

Based on the above data, answer the given subquestions.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph. Determine, for each statements in the given subquestions as true or false.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph. Determine, for each statements in the given subquestions as true or false.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph. Determine, for each statements in the given subquestions as true or false.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph. Determine, for each statements in the given subquestions as true or false.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph. Determine, for each statements in the given subquestions as true or false.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph. Determine, for each statements in the given subquestions as true or false.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph. Determine, for each statements in the given subquestions as true or false.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph. Determine, for each statements in the given subquestions as true or false.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph. Determine, for each statements in the given subquestions as true or false.

A graph is called a cluster graph if and only if it is a disjoint union of cliques. Recall that a clique is a graph where every vertex is adjacent to every other vertex.

The CLUSTER VERTEX DELETION problem is the following: Given an input graph $G$ and a parameter $k$, does there exist a set $S$ of at most $k$ vertices of $G$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph.

In the DISJOINT CLUSTER VERTEX DELETION problem we are given an input graph $G$, parameter $k$ and a set $S$ of vertices of $G$ of size $k+1$ such that the subgraph induced on $V(G) \setminus S$ is a cluster graph. We need to find if there exists a subset $T \subset V(G)$ of size at most $k$ which is disjoint from $S$ such that the subgraph induced on $V(G) \setminus T$ is a cluster graph. Determine, for each statements in the given subquestions as true or false.