Is the monitor cover problem of a graph NP-hard? 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 called the monitors).
I have the intuition that this problem is NP-hard. I have attempted to reduce the minimum set-cover problem but without success so far.
This problem occurs in Boolean tomography problem in computer networks.
The nodes in $M$ are called the monitors, therefore I call the problem monitor cover problem of a graph.
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)$.
 A: 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.
A: 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.
