prove by induction on $n$ that $\lvert S\rvert\geq\lvert O^*\rvert/\log n$, hence completing the proof of the lemma. If $n\leq 2$, then the lemma is clearly true. Suppose that the lemma is true for all $m<n$. Notice that since the algorithm directly computes a maximum independent set of $I_M$, we have $\lvert S(I_M)\rvert=\lvert O^*_M\rvert\geq\lvert O^*\cap I_M\rvert$. By induction hypothesis, we know that $$\lvert S(I_L)\rvert\geq\frac{\lvert O^*_L\rvert}{\log(n/2)}\geq\frac{\lvert O^*\cap I_L\rvert}{\log n - 1} \mbox{ and } \lvert S(I_R)\rvert\geq\frac{\lvert O^*_R\rvert}{\log(n/2)}\geq\frac{\lvert O^*\cap I_R\rvert}{\log n - 1}.$$ Since $S(I_L)\cap S(I_R)=\emptyset$, we have $$\begin{aligned}
\lvert S\rvert=\max\{\lvert S(I_L)\cup S(I_R)\rvert, \lvert S(I_M)\rvert\} & \geq\max\{\frac{\lvert O^*\cap I_L\rvert + \lvert O^*\cap I_R\rvert}{\log n-1}, \lvert O^*\cap I_M\rvert\}\\
& \geq\max\{\frac{\lvert O^*\rvert - \lvert O^*\cap I_M\rvert}{\log n-1}, \lvert O^*\cap I_M\rvert\}.\end{aligned}$$ If $\lvert O^*\cap I_M\rvert\geq\lvert O^*\rvert/\log n$, then we are done. Otherwise, $$\begin{aligned}
\frac{\lvert O^*\rvert - \lvert O^*\cap I_M\rvert}{\log n-1}\geq\frac{\lvert O^*\rvert - \lvert O^*\rvert/\log n}{\log n-1}=\frac{\lvert O^*\rvert}{\log n},\end{aligned}$$ which proves the induction step.

#### Original problem.

To approximate the original problem in which [$\mathcal{P}_{{\texttt{vtx}}}$ ]{}consists of all types of paths (i.e., {[$\ulcorner$]{}, [$\llcorner$]{}, [$\urcorner$]{}, [$\lrcorner$]{}, $|$, $-$}), we run the above algorithm four times once for each of the four types of paths (recall that we defined no-bend paths as [$\llcorner$]{}-type paths), and then return the 