1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Since the thing your optimizing doesn't care about the edges, you might-as-well specify "connected subgraph" rather than "subtree". ​ ​ $\endgroup$ – user12859 Feb 9 '16 at 17:15
  • $\begingroup$ @SamM The weights are non-negative and yes. We want to maximize the sum of weights while also including the vertices in $Q$. (I edited my post - I had forgotten to add the detail about non-negative weights) $\endgroup$ – Spiros Feb 9 '16 at 23:11
  • $\begingroup$ Providing guarantees would be ideal. As for the others, I edited my initial post to address them. $H$ has to be connected and degree is computed in $H$. $\endgroup$ – Spiros Feb 11 '16 at 12:21
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.