Prize collecting Steiner tree on graph without weights on edges

Question

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.

Answer 1

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.