3
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • $\begingroup$ @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.) $\endgroup$
    – MEL
    Jan 17, 2015 at 11:21
  • 2
    $\begingroup$ Why not just make a clique over all the nodes? That will support any set of paths you want $\endgroup$
    – Ryan Williams
    Jan 17, 2015 at 18:02
  • 2
    $\begingroup$ I edited the question for mathematical clarity. Feel free to roll-back or edit further. $\endgroup$
    – Kaveh
    Jan 18, 2015 at 3:31
  • 2
    $\begingroup$ 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). $\endgroup$
    – Kaveh
    Jan 18, 2015 at 11:26
  • 1
    $\begingroup$ Computer Science has a broader scope. Our scope is narrower, see tour and help center. $\endgroup$
    – Kaveh
    Jan 19, 2015 at 22:04

1 Answer 1

Reset to default
5
$\begingroup$

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: 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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – MEL
    Jan 19, 2015 at 0:43
  • $\begingroup$ @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. $\endgroup$
    – Radu GRIGore
    Jan 19, 2015 at 7:53
  • $\begingroup$ 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? $\endgroup$
    – MEL
    Jan 19, 2015 at 9:55
  • 1
    $\begingroup$ @MEL, it would be off-topic here to discuss at length such basic matters. Sorry. You could ask on cs.stackexchange.com. Also, I should say that I agree with Kaveh: an answer that discusses a heuristic/approximation would be interesting. $\endgroup$
    – Radu GRIGore
    Jan 20, 2015 at 9:35
  • $\begingroup$ Okay. I will update the questions. EDIT: Done. $\endgroup$
    – MEL
    Jan 20, 2015 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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