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?

$\endgroup$
8
  • 2
    $\begingroup$ They are names of vertices. Nothing more. $\endgroup$ Oct 31 '20 at 21:03
  • 1
  • $\begingroup$ @YuvalFilmus - but there are $n$ vertices in $V$ and there are $n+1$ $x_i$'s and $n+1$ $y_i$'s. $\endgroup$ Nov 1 '20 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$ Nov 1 '20 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.
    Nov 1 '20 at 1:41
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$.

$\endgroup$

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.