Is it NP-hard to find the min set of nodes in a graph so that the set of paths joining them cover all the nodes?

Question

Given a directed graph $G=(V,A)$ and given for every pair of nodes $(i,j)$ a valid path $P(i,j)=(v_1=i,...,v_l=j)$ on $G$. Find a minimum set of nodes $M$ such that $\bigcup_{(i,j)\in M\times M}P(i,j)=V$ (i.e. all the nodes are covered by at least one path between the selected nodes).

I have attempted to reduce the minimum set-cover problem but without success so far.

The even more general problem can be defined in terms of a given function $P:V\times V \rightarrow 2^V$. Find a minimum cardinality set $M\subseteq V$ such that $\forall i \in V, \exists (a,b) \in M \times M: i \in P(a,b)$.

Answer 1

The problem is indeed NP-hard, and cannot even be well-approximated in polynomial time. To see this, consider an instance $(\mathcal{F}, V)$ of the set cover problem. We construct an instance of the monitor cover problem as follows. The vertex set is $\mathcal{F}_1 \cup \mathcal{F}_2 \cup V$, where $\mathcal{F}_1$ and $\mathcal{F}_2$ are two copies of $\mathcal{F}$. If $a,b \in \mathcal{F}_1$ let $P(a,b)=\mathcal{F}_1$. Similarly, if $a,b \in \mathcal{F}_2$, let $P(a,b)=\mathcal{F}_2$. If $a \in \mathcal{F}_1$ and $b \in \mathcal{F}_2$ and $a$ and $b$ correspond to the same set of $\mathcal{F}$, let $P(a,b)=\{a,b\} \cup X$, where $X \subseteq V$ is the set of vertices in $a$. For all other pairs of vertices $a,b$, let $P(a,b)=\{a,b\}$. Let $M \subseteq \mathcal{F}_1 \cup \mathcal{F}_2 \cup V$ be an optimal solution to this monitor cover instance. Let $\mathcal{S} \subseteq \mathcal{F}$ be an optimal solution to the set cover instance. Observe that $\mathcal{S}_1 \cup \mathcal{S}_2$ is a feasible solution to the monitor cover instance, where $\mathcal{S}_1$ and $\mathcal{S}_2$ are the copies of $\mathcal{S}$ in $\mathcal{F}_1$ and $\mathcal{F}_2$. On the other hand, it is easy to check that $|M| \geq |\mathcal{S}|$. Thus, if we can solve monitor cover in polynomial time, we would get a $2$-approximation algorithm for set cover. However, it is well-known that for every $\epsilon > 0$, set cover does not admit a $(1-\epsilon) \log n$-approximation algorithm, where $n$ is the size of the universe.

Answer 2

So here is the reduction from 3-SAT; We are given boolean satisfiability problem of the form $$ (a_1 \vee b_1 \vee c_1) \wedge \dotsb \wedge (a_k \vee b_k \vee c_k), $$ where each of the $a_i,b_i,c_j \in \{x_1,\dotsc,x_n,\bar{x}_1,\dotsc,\bar{x}_n\}$ (so there are $n$ variables).

Let $N$ be an integer to be determined later. Here is the graph we are constructing. First, the vertex set:

• Two vertices, $x_i$, $\bar{x}_i$.
• One 'terminal' vertex $T$.
• One vertex, $C_i$ for each clause in the boolean expression.
• Vertices $v_{i,1},\dotsc,v_{i,N}$ for each $i=1,\dotsc,n$.

We describe the edges as a union of paths: These are the designated paths for the pairs $(x_i,T)$ and $(\bar{x}_i,T)$.

From $x_i$ (and $\bar{x}_i)$ there is the path starting as $x_i,v_{i,1},\dotsc,v_{i,N}$, then passing through all vertices corresponding to clauses containing the variable $x_i$ (in some order), and finally ending at $T$.

All other paths from some vertex to another is simply an edge between them.

Now, an assignment making the formula true, corresponds to choosing $n$ paths, (picking if $x_i$ or $\bar{x}_i$ is true) each passing through the sequence of auxiliary vertices $v_{i,1},\dotsc,v_{i,N}$. This covers all vertices, except $n$ vertices $x_i$ or $\bar{x}_i$, for which we need to cover, say via the direct edge to $T$. Hence, $2n$ paths in total.

Now, if we DO NOT choose any of the long paths $x_i \to T$ or $\bar{x}_i \to T$, we need to cover $x_i,v_{i,1},\dotsc,v_{i,N}$ by some other means, but this requires at least $N/2$ extra paths. So, if $N$ is large, this is worse than $2n$.

Hence, we can path-cover the above graph with $2n$ paths, if and only if the formula is satisfiable.