The Primal-Dual Method

In both primal and dual rounding algorithm we need to solve an LP

It can require long computational time. However, the dual rounding algorithms do not actually need an optimal solution but only a solution that is feasible for both problems and tightly satisfies certain constraints. Primal-dual algorithms search for such solutions.

Recall: the Set Cover Problem

See here.

Feedback Vertex Set in Undirected Graphs

Problem Setting

Given:

an undirected graph $G=(V,E)$
weights $w_i\geq 0$ for each $i\in V$

Find a $S\subseteq V$ s.t.

$G[V\backslash S]$ is acyclic
$\sum_{i\in S}w_i$ is minimum

In other words: Choose the minimum-cost subset $S$ of $V$ s.t. every cycle in $G$ contains a node in $S$.

We say that $S$ hits every cycle in $G$.

IP Formulation

Let $\mathcal C$ be the set of all cycles in $G$. We define a variable $x_i$ for each $i\in V$. $$ \min\sum_{i\in V}w_ix_i $$ s.t. $$ \sum_{i\in C}x_i\geq1\forall C\in\mathcal C\land x_i\in{0,1}\forall i\in V $$ Note that the number $|\mathcal C|$ of cycles in the graphs is exponential. The number of constraints in the primal program is exponential. With primal-dual method we do not need to solve an IP or LP.

Dual

We relax $x_i\in\{0,1\}$ with $x_i\geq0,\forall i\in V$, and take the dual: $$ \max\sum_{C\in\mathcal C}y_C $$ s.t. $$ \sum_{C\in\mathcal C:i\in C}y_C\leq w_i\forall i\in V\land y_C\geq0\forall C\in\mathcal C $$ The number of variables is exponential but we need only a polynomial time of non-zero variables.

Primal-Dual Algorithm

$y=0,S=\emptyset$

while there exists a cycle $C$ in $G$, do

Increase $y_C$ until there is some $\ell\in C$ s.t. $\sum_{C'\in\mathcal C:\ell\in C}y_{C'}=w_\ell$
$S=S\cup\{\ell\}$
Remove $\ell$ from $G$
Repeatedly remove vertices of degree one from $G$

Return $S$

We can increase $y_C$ by $$ \min_{i\in C}(w_i-\sum_{C':i\in C'}y_{C'}). $$ We remove the vertices of degree one as they cannot belong to any cycle.

We analyze as in set cover $$ \sum_{i\in S}w_i=\sum_{i\in S}\sum_{C:i\in C}y_C=\sum_{C\in\mathcal C}|S\cap C|y_C. $$ $|S\cap C|$ is the number of nodes of $S$ that are in the cycle $C$.

If we can bound $|S\cap C|\leq\alpha$, then $$ \sum_{i\in S}w_i\leq\alpha\sum_{C\in\mathcal C}y_C\leq\alpha\cdot OPT. $$ If we choose an arbitrary cycle $C$, $|S\cap C|$ can be arbitrarily large. We need to choose a particular cycle $C$.

Lemma: For any path $P$ of vertices of degree two in the graph, the algorithm will choose at most one vertex from $P$, $|S\cap P|\leq1$.

Lemma: In any graph $G$ that has no vertices of degree one, there exists a cycle with at most $2\lceil\log_2|V|\rceil$ vertices of degree three or more and it can be found in polynomial time.

We then revise the algorithm:

$y=0,S=\emptyset$

Repeatedly remove vertices of degree one from $G$.

while there exists a cycle $C$ in $G$, do

Find a cycle $C$ with $\leq2\lceil\log_2|V|\rceil$ vertices of degree $\geq3$
Increase $y_C$ until there is some $\ell\in C$ s.t. $\sum_{C'\in\mathcal C:\ell\in C}y_{C'}=w_\ell$
$S=S\cup\{\ell\}$
Remove $\ell$ from $G$
Repeatedly remove vertices of degree one from $G$

Return $S$

Theorem: The primal-dual algorithm is an $(4\lceil\log_2|V|\rceil)$-approximation algorithm for the feedback vertex set problem in undirected graphs.

Observations

In some case we must carefully choose the variable to increase

It can be useful to choose a variable that is small or minimal in some sense

There is a primal-dual $2$-approximation algorithm based on a more sophisticated IP formulation

The Shortest s-t Path Problem

Problem Setting

Given:

an undirected graph $G=(V,E)$
weights $c_e\geq0$ for each $e\in E$
two vertices $s$ and $t$ in $V$

Find a minimum cost path from $s$ to $t$

The problem is in $P$ by Dijkstra's algorithm, Bellman-Ford...

We devise a primal-dual algorithm.

Analysis

Let $\mathcal S$ be the set of $s-t$ cuts in $G,\mathcal S=\{S\subseteq V:s\in S,t\not\in S\}$

$\delta(S)$: edges with endpoints in $S$ and $V\backslash S$

IP formulation $$ \min\sum_{e\in E}c_ex_e $$ s.t. $$ \sum_{e\in\delta(S)}x_e\geq1\forall S\in\mathcal S\land x_e\in{0,1}\forall e\in E $$ For any solution $x$, let $G'=(V,E'),E'=\{e\in E|x_e=1\}$

If $x$ is feasible

By the constraints, there is least one edge in $\delta(S)$, for any cut $S$.
The size if the minimum $s-t$ cut in $G'$ is at least $1$.
By max-flow/min-cut theorem, the maximum flow is at least $1$, then there exists an $s-t$ path in $G'$

If $x$ is not feasible

By the constraints, there is a cut $S$ for which no edge in $E'$ is in $\delta(S)$
The size if the minimum $s-t$ cut in $G'$ is $0$
By max-flow/min-cut theorem, the maximum flow is $0$, then there is no $s-t$ path in $G'$

The dual of LP relaxation $$ \max\sum_{S\in\mathcal S}y_S $$ s.t. $$ \sum_{S\in\mathcal S:e\in\delta(S)}y_S\leq c_e\forall e\in E\land y_S\geq0\forall S\in\mathcal S $$

Primal-Dual Algorithm

$y=0,F=\emptyset$

while there is no $s-t$ path in $(V,F)$ do

Let $C$ be the connected component of $(V,F)$ containing $s$
Increase $y_C$ until there is an edge $e'\in\delta(C)$ s.t. $\sum_{S\in\mathcal S:e'\in\delta(S)}y_S=c_{e'}$
$F=F\cup\{e'\}$

Remove from $F$ any edge that is not on an $s-t$ path in $(V,F)$

Let $P$ be the obtained path

return $P$

We increase a variable $y_C$ associated to an $s-t$ cut $C$ s.t. $F\cap\delta(C)=\emptyset$

As before, we choose the smallest of such cuts

Differently from before, we don't return $F$ but a subset of $F$

Theorem: The primal-dual algorithm finds a shortest $s-t$ path.