Cheap and Secure Web Hosting Provider : See Now

# [Solved]: Prize collecting Steiner tree on graph without weights on edges

, ,
Problem Detail:

I have been trying to find an easy-to-implement approximation algorithm on the problem of Prize collecting Steiner tree on node-weighted graph without weights on the edges. The closest I have come is the one in The prize collecting Steiner tree problem: Theory and Practice by Johnson, Minkoff and Phillips, but the GW algorithm provided won't work without weights on edges (I think).

The problem I'm trying to solve is:

Given a graph $G=(V,E,w)$, $w$ being a function assigning non-negative weights to nodes, and a set of query nodes $Q$, find a connected subgraph $H$ of $G$, spanning all nodes in $Q$, and also maximizing the following function

$$f(H) = \sum_{v\in V_H}w(v) + \min_{v \in V_H}\deg_H(v)$$

with $V_H \subseteq V$ being the set of nodes in $H$.

Keep in mind I need an easy to implement approximation algorithm to use as a baseline for comparison, so any LP or SDP ways to solve it, won't be of much help.

Something seems not quite right. Your problem can be solved in polynomial time, so I doubt that it is NP-hard. Let me explain how to solve it in polynomial time.

First note that there exists a positive integer $t$ such that your problem is equivalent to finding $H$ that maximizes

$$f_t(H) = \sum_{v \in V_H} w(v) + t,$$

subject to the additional constraint that $\deg_H(v) \ge t$ for all $v \in V_H$. Also, $1 \le t \le n$, where $n=|V|$ is the number of vertices in $G$, so there are at most $O(n)$ possible values for $t$. That means we can try them all and, for each $t$, find the optimal choice of $H$. Given $t$, maximizing $f_t(H)$ can be done by a simple iterative fixpoint algorithm, where you keep as many vertices of $V$ as possible.

In this way, we obtain the following algorithm:

1. For $t := 1,2,\dots,n$:

a. Repeatedly delete vertices of degree $\le t$ until there are no more to delete. In other words, while there exists $x \in V$ such that $\deg(x) \le t$, delete $x$ from $V$.

b. If there exists a single connected component of $G$ that contains all vertices of $Q$, set $H$ to be that component, compute $f(H)$, and if this $f(H)$ is better than anything found before, remember this $H$.

Correctness follows from the above discussion. This can be implemented so that its running time is $O((n+m) \alpha(n))$, where $n=|V|$ and $m=|E|$ and $\alpha(\cdot)$ is the inverse Ackerman function.