0
$\begingroup$

Given undirected graph $G=(V, E)$, function of weights of edges $c: E \rightarrow \mathbb{Z}$, function of weights of vertices $\pi: V \rightarrow \mathbb{Z}$ and vertex $r$, find connected subgraph of $G$, containing $r$, and such that sum of weights of edges minus sum of weights of vertices is minimized.

Here is primal linear program for this problem: \begin{align} &\text{minimize} &\sum_{e\in E}c(e)x_e - \sum_{v \in V} \pi (v) y_v \\ &\text{subject to} &\sum_{e \in E(S, V\setminus S)} x_e - y_v &\geq 0 &&\forall S \subseteq V \setminus \{r\}, S \neq \emptyset, \forall v \in S \tag1\label1 \\ &&x_e &\geq 0 &&\forall e \in E \tag2\label2 \\ &&y_v &\leq 1 &&\forall v \in V \setminus \{r\} \tag3\label3 \\ &&y_r &= 1 \tag4\label4 \end{align}

I want to find dual program. I know how to find dual program in simple cases, but in more complex cases (especially with sums over sets), I get completely lost.

Following RobPratt answer, I wrote this constraints: \begin{align} & \beta_{v} + \sum_{S \subseteq V \setminus \{r\}, S \neq \emptyset} \alpha_{S, v} = \pi (v) && \forall_{v \in V \setminus \{r\} }\\ & \lambda + \sum_{S \subseteq V \setminus \{r\}, S \neq \emptyset} \alpha_{S, v} = \pi(r) \\ & \sum\limits_{\substack{S \subseteq V \setminus \{r\} \\ S \neq \emptyset \\ e=\{u, v\} \\ u \in S \\ v \in V \setminus S}} \sum_{v \in S} \alpha_{S, v} \leq c(e) && \forall_{e \in E} \end{align}

$\endgroup$
2
  • 1
    $\begingroup$ Good to see that Alex reformed to do math $\endgroup$
    – Babu
    Commented Jun 26, 2022 at 22:05
  • $\begingroup$ @EthakkaappamwithChai it's almost the same as ultraviolence so I can't complain $\endgroup$
    – abc2343
    Commented Jul 1, 2022 at 16:11

1 Answer 1

1
$\begingroup$

First introduce dual variables for each set of constraints (except the zero lower bounds $(2)$). For constraint $(1)$, let $\alpha_{S,v} \ge 0$ for all $S \subseteq V \setminus \{r\}$ such that $S \neq \emptyset$ and for all $v \in S$. For constraint $(3)$, let $\beta_v \le 0$ for all $v \in V \setminus \{r\}$. For constraint $(4)$, let $\gamma$ be free. The dual objective is to maximize $$0 \sum_{S,v} \alpha_{S,v} + 1 \sum_{v \in V \setminus \{r\}} \beta_v + 1 \gamma.$$

I'll leave the dual constraints to you. There will be one set of $\le$ constraints corresponding to $x_e$ and one set of $=$ constraints corresponding to $y_v$.

$\endgroup$
4
  • $\begingroup$ Thanks! Could you explain why $\beta_v$ should be less than zero? $\endgroup$
    – abc2343
    Commented Jul 1, 2022 at 15:57
  • 1
    $\begingroup$ $\beta_v \le 0$ because the primal constraint is $\le$ in a minimization problem. $\endgroup$
    – RobPratt
    Commented Jul 1, 2022 at 16:19
  • $\begingroup$ I've edited my answer, would you mind taking a look if this constraints are correct? $\endgroup$
    – abc2343
    Commented Jul 1, 2022 at 19:15
  • $\begingroup$ Your $\le$ constraint has $u$ and $v$ backwards and should not have a second $\sum_v$. Your equality constraints are missing some minus signs. Also, the dual constraint for $y_r$ should not contain $\alpha$. I recommend explicitly writing everything out for a small example, say with $3$ nodes. $\endgroup$
    – RobPratt
    Commented Jul 1, 2022 at 19:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .