# Find dual linear program to modified Steiner tree problem

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}

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

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$$.
• Thanks! Could you explain why $\beta_v$ should be less than zero? Commented Jul 1, 2022 at 15:57
• $\beta_v \le 0$ because the primal constraint is $\le$ in a minimization problem. Commented Jul 1, 2022 at 16:19
• 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. Commented Jul 1, 2022 at 19:35