<p>This problem is NP-complete, even for the special case $|P_k|\le 3$. I will give a reduction from Vertex Cover. I will refer to the sets $P_1,\ldots,P_k$ in the question as <em>constraints</em>: binary or ternary, depending on their cardinality.</p>

<p>Let $(V',E',k)$ be an instance of <a href="http://en.wikipedia.org/wiki/Vertex_cover" rel="nofollow">Vertex Cover</a>: Is there a subset $S$ of $k$ vertices from $V'$ such that $S$ covers (that is, intersects) all edges in $E'$?</p>

<p>We add a distinguished vertex $\bullet$; that is, $V=V'\cup\{\bullet\}$. We add binary constraints for all pairs of vertices in $V'$: for each $\{i,j\}\subseteq V'$, we add the constraint $\{i,j\}$. We then add ternary constraints for each edge in $E'$: for each $\{i,j\}\in E'$, we add the constraint $\{i,j,\bullet\}$.</p>

<p>We ask whether there is a graph with $\binom{|V'|}{2}+k$ edges that satisfies the above constraints. The answer (yes or no) is an answer to the Vertex Cover question.</p>

<p>Why would that work? Because of the binary constraints, we know that edge $\{i,j\}$ is selected. So, the only task that remains is to pick between $\{i,\bullet\}$ and $\{j,\bullet\}$. That's exactly the task we have in the original Vertex Cover problem: Pick which endpoint of an edge we use to cover it.</p>

CC BY-SA 3.0
2015-01-19T00:43:11.627Z
I'd like to ask some questions in detail. First, do you mean that the binary and ternary constraints added are equivalent to the given sets? Why? Second, why would we ask whether there is a graph with (k plus combination of taking 2 from the vertices) edges that satisfies the above constraints? Is it exactly the output we want? If so, why? Thanks.
MEL
CC BY-SA 3.0
2015-01-19T07:53:11.053Z
@MEL, here's an example. Suppose someone asks if there is a vertex cover of size $2$ for the graph $1-2-3-4-5$. We build the constraints $\{1,2,\bullet\}$, $\{2,3,\bullet\}$, ..., $\{4,5,\bullet\}$, and also binary ones for 10 pairs of numbers. Then we ask for a graph that satisfies these constraints and uses at most 10+2 edges. The graph we get back will contain a clique for the numbers, with 10 edges. The remaining 2 edges are $\{2,\bullet\}$ and $\{4,\bullet\}$. These are enough to satisfy the ternary constraints: there are paths $1-2-\bullet$ and $2-\bullet-3$ and so on.
Radu GRIGore
CC BY-SA 3.0
2015-01-19T09:55:27.493Z
No offense, I think you didn't answer my questions. I know that these constraints are satisfied. But how are they related to the original problem?
MEL
CC BY-SA 3.0
2015-01-20T09:35:27.513Z
@MEL, it would be off-topic here to discuss at length such basic matters. Sorry. You could ask on http://cs.stackexchange.com/. Also, I should say that I agree with Kaveh: an answer that discusses a heuristic/approximation would be interesting.
Radu GRIGore
CC BY-SA 3.0
2015-01-20T09:55:47.163Z
Okay. I will update the questions. EDIT: Done.
MEL
CC BY-SA 3.0
2015-01-18T10:24:26.370Z
2015-01-18T17:03:21.227Z
2015-01-18T17:03:21.227Z
Radu GRIGore
<p>Consider the following problem:</p>

<p>Input: a list of subsets $P_1, P_2, \ldots, P_k \subseteq V = \{1, \ldots, n\}$<br>
Output: a graph $G = (V,E)$ with minimum number of edges such that </p>

<ul>
<li>for every $P_i$ there is a path in $G$ which has $P_i$ as its set of vertices.   </li>
</ul>

<p>Has this problem been studied?<br>
Does it have a name?<br>
What is the fastest known algorithm for solving it?</p>

CC BY-SA 3.0
2015-01-17T11:21:55.770Z
@Juho "The sequence of the nodes on a particular path is not known". Sorry I can't find the proper terminology for it. Let's say we have five nodes, {a,b,c,d,e}. And we know that there are two paths. Path 1 has {a,b,c} on it, but we don't know which is the first, or the last, etc. Now we have Path 2, which have four nodes on it, {a,b,d,e}. What graphs can we get these two paths from? (One solution to this example is a linear graph b-c-a-d-b-e.)
MEL
CC BY-SA 3.0
2015-01-17T12:26:41.473Z
@Juho I've updated my problem. I hope this helps.
MEL
CC BY-SA 3.0
2015-01-17T18:02:31.787Z
Why not just make a clique over all the nodes? That will support any set of paths you want
Ryan Williams
CC BY-SA 3.0
2015-01-18T03:03:01.893Z
@RyanWilliams Sorry, I should add one more constraint. The goal is to minimize the number of (possible) paths. I will update the post as well.
MEL
CC BY-SA 3.0
2015-01-18T03:31:32.650Z
I edited the question for mathematical clarity. Feel free to roll-back or edit further.
Kaveh
CC BY-SA 3.0
2015-01-18T11:26:28.200Z
I hope that I haven't change the question (I replaced the number of paths with the number of edges as I guessed that you just want to minimize the graph, if for some reason you really care about the number of paths being minimum then you should change "minimum number of edges" to "minimum number of paths"). Also I am guessing that you don't want an optimal solution, and considering Radu's answer you may want to add that explicitly (e.g. by asking if there are any approximation or heuristic algorithms for the problem).
Kaveh
CC BY-SA 3.0
2015-01-19T00:10:21.183Z
@Kaveh Thanks for your edit! Originally I wanted to asked about the number of paths indeed. I was daydreaming something like this: If we know that some variables are in association, how can we discover how they are associated? The paths represents the associations between variables. The input subsets represent the variables in association inferred in each trial. So to minimize number of paths is to minimize unnecessary associations. But I am not professional in CS (I should have posted it in Computer Science), and I can't recognize the difference. Plus, Radu has given a great answer.
MEL
CC BY-SA 3.0
2015-01-19T00:12:18.390Z
@Kaveh So I think it is better to treat them as additional questions. I will ask about approximations and heuristics like this as well.
MEL
CC BY-SA 3.0
2015-01-19T22:04:27.823Z
[cs.se] has a broader scope. Our scope is narrower, see [tour] and [help/on-topic].
Kaveh
<ds.algorithms><graph-theory><graph-algorithms>
Graph with minimum number of edges having given sets of nodes as its paths
MEL
# Graph with minimum number of edges having given sets of nodes as its paths

(Asked by: username_0 on 2015-01-17)

Consider the following problem:

Input: a list of subsets $P\_1, P\_2, \ldots, P\_k \subseteq V = \{1, \ldots, n\}$  
Output: a graph $G = (V,E)$ with minimum number of edges such that

* for every $P\_i$ there is a path in $G$ which has $P\_i$ as its set of vertices.

Has this problem been studied?  
Does it have a name?  
What is the fastest known algorithm for solving it?

**Tags:** ds.algorithms, graph-theory, graph-algorithms

> **Comments:**
> **username_0**: @Juho "The sequence of the nodes on a particular path is not known". Sorry I can't find the proper terminology for it. Let's say we have five nodes, {a,b,c,d,e}. And we know that there are two paths. Path 1 has {a,b,c} on it, but we don't know which is the first, or the last, etc. Now we have Path 2, which have four nodes on it, {a,b,d,e}. What graphs can we get these two paths from? (One solution to this example is a linear graph b-c-a-d-b-e.)  
> **username_0**: @Juho I've updated my problem. I hope this helps.  
> **username_1**: Why not just make a clique over all the nodes? That will support any set of paths you want  
> **username_0**: @RyanWilliams Sorry, I should add one more constraint. The goal is to minimize the number of (possible) paths. I will update the post as well.  
> **username_2**: I edited the question for mathematical clarity. Feel free to roll-back or edit further.  
> **username_2**: I hope that I haven't change the question (I replaced the number of paths with the number of edges as I guessed that you just want to minimize the graph, if for some reason you really care about the number of paths being minimum then you should change "minimum number of edges" to "minimum number of paths"). Also I am guessing that you don't want an optimal solution, and considering Radu's answer you may want to add that explicitly (e.g. by asking if there are any approximation or heuristic algorithms for the problem).  
> **username_0**: @username_2 Thanks for your edit! Originally I wanted to asked about the number of paths indeed. I was daydreaming something like this: If we know that some variables are in association, how can we discover how they are associated? The paths represents the associations between variables. The input subsets represent the variables in association inferred in each trial. So to minimize number of paths is to minimize unnecessary associations. But I am not professional in CS (I should have posted it in Computer Science), and I can't recognize the difference. Plus, Radu has given a great answer.  
> **username_0**: @username_2 So I think it is better to treat them as additional questions. I will ask about approximations and heuristics like this as well.  
> **username_2**: [cs.se] has a broader scope. Our scope is narrower, see [tour] and [help/on-topic].  

---

## 1 answers

### Answer by username_3 on 2015-01-18. Score: 5 | Accepted answer

This problem is NP-complete, even for the special case $|P\_k|\le 3$. I will give a reduction from Vertex Cover. I will refer to the sets $P\_1,\ldots,P\_k$ in the question as *constraints*: binary or ternary, depending on their cardinality.

Let $(V',E',k)$ be an instance of [Vertex Cover](http://en.wikipedia.org/wiki/Vertex_cover): Is there a subset $S$ of $k$ vertices from $V'$ such that $S$ covers (that is, intersects) all edges in $E'$?

We add a distinguished vertex $\bullet$; that is, $V=V'\cup\{\bullet\}$. We add binary constraints for all pairs of vertices in $V'$: for each $\{i,j\}\subseteq V'$, we add the constraint $\{i,j\}$. We then add ternary constraints for each edge in $E'$: for each $\{i,j\}\in E'$, we add the constraint $\{i,j,\bullet\}$.

We ask whether there is a graph with $\binom{|V'|}{2}+k$ edges that satisfies the above constraints. The answer (yes or no) is an answer to the Vertex Cover question.

Why would that work? Because of the binary constraints, we know that edge $\{i,j\}$ is selected. So, the only task that remains is to pick between $\{i,\bullet\}$ and $\{j,\bullet\}$. That's exactly the task we have in the original Vertex Cover problem: Pick which endpoint of an edge we use to cover it.

> **Comments:**
> **username_0**: I'd like to ask some questions in detail. First, do you mean that the binary and ternary constraints added are equivalent to the given sets? Why? Second, why would we ask whether there is a graph with (k plus combination of taking 2 from the vertices) edges that satisfies the above constraints? Is it exactly the output we want? If so, why? Thanks.  
> **username_3**: @username_0, here's an example. Suppose someone asks if there is a vertex cover of size $2$ for the graph $1-2-3-4-5$. We build the constraints $\{1,2,\bullet\}$, $\{2,3,\bullet\}$, ..., $\{4,5,\bullet\}$, and also binary ones for 10 pairs of numbers. Then we ask for a graph that satisfies these constraints and uses at most 10+2 edges. The graph we get back will contain a clique for the numbers, with 10 edges. The remaining 2 edges are $\{2,\bullet\}$ and $\{4,\bullet\}$. These are enough to satisfy the ternary constraints: there are paths $1-2-\bullet$ and $2-\bullet-3$ and so on.  
> **username_0**: No offense, I think you didn't answer my questions. I know that these constraints are satisfied. But how are they related to the original problem?  
> **username_3**: @username_0, it would be off-topic here to discuss at length such basic matters. Sorry. You could ask on http://cs.stackexchange.com/. Also, I should say that I agree with username_2: an answer that discusses a heuristic/approximation would be interesting.  
> **username_0**: Okay. I will update the questions. EDIT: Done.  

---

