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?

$\endgroup$
  • $\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 '15 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 '15 at 18:02
  • 2
    $\begingroup$ I edited the question for mathematical clarity. Feel free to roll-back or edit further. $\endgroup$ – Kaveh Jan 18 '15 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 '15 at 11:26
  • 1
    $\begingroup$ Computer Science has a broader scope. Our scope is narrower, see tour and help center. $\endgroup$ – Kaveh Jan 19 '15 at 22:04
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.

$\endgroup$
  • $\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 '15 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 '15 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 '15 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 '15 at 9:35
  • $\begingroup$ Okay. I will update the questions. EDIT: Done. $\endgroup$ – MEL Jan 20 '15 at 9:55

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.