1
$\begingroup$

In the book on algorithms by Cormen et.al, the problem 26-2 describes how to obtain a min-path cover for a DAG via max-flow. I have a question about the notation. First, let me quote the problem here:

A path cover of a directed graph $G = (V, E)$ is a set $P$ of vertex-disjoint paths such that every vertex in $V$ is included in exactly one path in $P$. Paths may start and end anywhere, and they may be of any length, including $0$. A minimum path cover of $G$ is a path cover containing the fewest possible paths.

a. Give an efficient algorithm to find a minimum path cover of a directed acyclic graph $G =(V, E)$ (Hint: Assuming that $V = {1, 2, ... , n}$, construct the graph $G' = (V',E')$, where:

$$V' = \{x_0,x_1,\dots x_n\} \cup \{y_0, y_1, \dots y_n\} $$ $$E'=\{(x_0,x_i):i \in V\} \cup \{(y_i,y_0) : i \in V\} \cup \{(x_i,y_i):(i,j) \in E\}$$ and run a maximum-flow algorithm.)

What are the $x_i$ and $y_i$ here? Am I missing something obvious?

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ They are names of vertices. Nothing more. $\endgroup$
    – Yuval Filmus
    Commented Oct 31, 2020 at 21:03
  • 1
    $\begingroup$ Cross-posted: cs.stackexchange.com/q/131775/755, math.stackexchange.com/q/3889234/14578. Please do not post the same question on multiple sites. I've mentioned this previously. $\endgroup$
    – D.W. ♦
    Commented Oct 31, 2020 at 21:05
  • $\begingroup$ @YuvalFilmus - but there are $n$ vertices in $V$ and there are $n+1$ $x_i$'s and $n+1$ $y_i$'s. $\endgroup$
    – Rohit Pandey
    Commented Nov 1, 2020 at 0:44
  • $\begingroup$ @D.W. deleted the math.stackexchange one. In this case, admittedly, I didn't tailor too much to individual sites. But the meta discussion you linked suggests it's okay to cross-post if you do that? $\endgroup$
    – Rohit Pandey
    Commented Nov 1, 2020 at 0:46
  • $\begingroup$ I suggest putting more effort into improving the quality of your question instead of on spreading it more widely. When you're asking basically the same question on both sites (just with paraphrased words), I don't consider that tailoring. That answer also recommends cross-linking both ways as well. $\endgroup$
    – D.W. ♦
    Commented Nov 1, 2020 at 1:41

1 Answer 1

Reset to default
1
$\begingroup$

The graph $G'$ has $2n+2$ vertices. We give them the names $x_0,\ldots,x_n,y_0,\ldots,y_n$ to make it easy to refer to them. So $x_i,y_i$ are just names of vertices. They have no value, and do not refer to anything. In that regard, they are akin to indeterminates.

What might be confusing you is the existence of a different graph $G$, which has $n$ vertices. The vertices $x_i,y_i$ are just vertices – they are not variables referring to vertices of $G$. The "value" of $x_i$ is just $x_i$.

Improve this answer
$\endgroup$

Your Answer

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

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