Question 17: We define an overlap graph OG(\mathcal{S}) associated wi…

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 $|\operatorname{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 $|\operatorname{ov}(u, v)| \geqslant |\operatorname{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?