2
$\begingroup$

Consider the node-weighted steiner problem:

Input: a graph $G=(V,E)$, a set $T\subseteq V$ of terminals, a weight function $w: V\setminus T \to \mathbb{R}_+$.

Output: a minimum weight subset $S \subseteq V\setminus T$ of vertices such that $G[T\cup S]$ is connected.

This problem is known to be at least as hard as Set Cover. However, I am interested in a more special case of node-weighted steiner tree, in which:

  1. Each steiner node is incident to exactly 2 terminals of $T$
  2. $T$ is an independent set.

If I added a third condition that every pair of steiner nodes are adjacent, then this would be equivalent to an edge cover problem, which can be solved in polynomial time.

Hence, my special case lies somewhere in the middle between very hard to approximate (node weighted steiner tree), and exactly solvable (edge cover).

Since I don't know whether this is in P or NP-hard or to what extent it is approximable, any ideas about algorithms or hardness results on this problem would be welcome. Thanks!

$\endgroup$
0
3
$\begingroup$

To answer my own question, I have found that this problem is indeed NP-Hard via a reduction from the Cactus Augmentation Problem (which is NP-hard).

In "Parameterized Algorithms to Preserve Connectivity" they show that a Cactus Augmentation Problem can be transformed into an equivalent Node-weighted Steiner Tree problem where each Steiner node is incident on exactly 2 terminals.

Hence, a polynomial time algorithm for my problem would imply a polynomial time algorithm for Cactus Augmentation which would mean P=NP.

$\endgroup$
2
  • 3
    $\begingroup$ "reduction to" -> "reduction from" :-) $\endgroup$
    – Neal Young
    Oct 6 '21 at 18:40
  • $\begingroup$ Thanks 🙏🙏🙏🙏🙏🙏 $\endgroup$ Oct 7 '21 at 2:25

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.