Advanced Algorithms Quiz 2: 4 August 2024 (May 2024 term)

Based on the above data, answer the given subquestions.

Consider the following graph. A triangle-free subset of seven vertices is highlighted. Find the size of the largest triangle-free subset of vertices in this graph.

Based on the above data, answer the given subquestions.

The TRIANGLE-FREEDOM problem is the following: the input is a simple undirected graph G and a positive integer k. An instance (G, k) is a YES-instance if and only if G has a subset S of at least k vertices that are triangle-free.
What can you say about TRIANGLE-FREEDOM? Check all that apply.

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 \rightarrow \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$?

Consider the following statements and answer the given 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 following statements and answer the given subquestions if they are true or false.

An adversary can provide randomized quicksort with an input array of length $n$ that forces the algorithm to run in $\omega(n \lg n)$ time on that input. (If you are not familiar with the $\omega$ asymptotic notation, it roughly translates as “at least’ ’. For example, we can say that it is possible to come up with an input that forces insertion sort to run for $\omega(n^2)$ steps.)

Recall that in the vertex cover problem, we are trying to find a smallest subset $S$ of vertices in a graph $G$ such that $G \setminus S$ is an independent set; in other words, for every edges $(u, v)$ in the graph $G$, we have that $\{u, v\} \cap S$ is non-empty.

Consider the algorithm that repeats the following steps as long as the graph has at least one edge available: select a vertex of maximum degree (say $w$), and include $w$ in the solution; thereafter, delete $w$ and all edges incident to $w$.

Based on the above data, answer the given subquestions.

Is it true that the algorithm always outputs a vertex cover?

Recall that in the vertex cover problem, we are trying to find a smallest subset $S$ of vertices in a graph $G$ such that $G \setminus S$ is an independent set; in other words, for every edges $(u, v)$ in the graph $G$, we have that $\{u, v\} \cap S$ is non-empty.

Consider the algorithm that repeats the following steps as long as the graph has at least one edge available: select a vertex of maximum degree (say $w$), and include $w$ in the solution; thereafter, delete $w$ and all edges incident to $w$.

Based on the above data, answer the given subquestions.

Consider the algorithm in the given question. Does the algorithm always output an optimal vertex cover?

Recall that in the vertex cover problem, we are trying to find a smallest subset $S$ of vertices in a graph $G$ such that $G \setminus S$ is an independent set; in other words, for every edges $(u, v)$ in the graph $G$, we have that $\{u, v\} \cap S$ is non-empty.

Consider the algorithm that repeats the following steps as long as the graph has at least one edge available: select a vertex of maximum degree (say $w$), and include $w$ in the solution; thereafter, delete $w$ and all edges incident to $w$.

Based on the above data, answer the given subquestions.

Consider the algorithm in the given question. Does the algorithm always output a 2-approximate vertex cover?

Recall that in the vertex cover problem, we are trying to find a smallest subset $S$ of vertices in a graph $G$ such that $G \setminus S$ is an independent set; in other words, for every edges $(u, v)$ in the graph $G$, we have that $\{u, v\} \cap S$ is non-empty.

Consider the algorithm that repeats the following steps as long as the graph has at least one edge available: select a vertex of maximum degree (say $w$), and include $w$ in the solution; thereafter, delete $w$ and all edges incident to $w$.

Based on the above data, answer the given subquestions.

Recall that the size of an optimal vertex cover is at most twice the size of a maximum matching of a graph G. Are there examples of graphs where the size of the optimal vertex cover is exactly equal to twice the size of its maximum matching? For example, this is not true for a path on three vertices: the size of both the maximum matching and minimum vertex cover is 1.

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.

The construction described here is a valid reduction from 3-SAT to 3-Coloring.

Based on the above data, answer the given subquestions.

The construction described here is a valid reduction from 3-Coloring to 3-SAT.

Based on the above data, answer the given subquestions.

Argue that to solve SCS, it is sufficient to find:

Based on the above data, answer the given subquestions.

Observe that for a given $\pi$, the length of the corresponding superstring $s(\pi)$, which is obtained by writing the input strings in the order $\left(s_{\pi(1)}, \ldots, s_{\pi(n)}\right)$ and merging adjacent strings, is given by:

$|s(\pi)| = \sum_{i=1}^{n} |s_i| - \sum_{i=1}^{n-1} \left|\text{ov}\left(s_{\pi(i)}, s_{\pi(i+1)}\right)\right|.$

The compression of $\pi$ is the sum of the overlaps of adjacent strings in the permutation $\pi$. Finding a shortest superstring is equivalent to:

Based on the above data, answer the given subquestions.

We define an overlap graph $OG(\mathcal{S})$ associated with $\mathcal{S}$ as follows: $OG(\mathcal{S})$ is a complete directed graph $(V, E)$ (that is, for every $s, t \in V$ there are edges $(s, t)$ and $(t, s)$), where $V = \mathcal{S}$, and the weight of an edge $(s, t)$ is $|\text{ov}(s, t)|$.

Let us say that an edge $(u, v)$ dominates another edge $(u', v')$, if they share head or tail (that is, $u = u'$ or $v = v'$) and $|\text{ov}(u, v)| \geqslant |\text{ov}(u', v')|$.

In terms of the overlap graph, the greedy algorithm goes through a list of all edges in $OG(\mathcal{S})$ in the nonincreasing order of their overlap and includes some of them in a solution. Specifically, the greedy algorithm does not include another edge if and only if

R1. it is dominated by an already chosen edge,
R2. it is not dominated but it would form a cycle.

What is the structure of the set of edges returned by the greedy algorithm?

Based on the above data, answer the given subquestions.

Does the greedy algorithm always produce the right answer?