Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question is similar to the one answered here but it's different for I'm defining paths as subgraphs, not sequences of vertices.

Consider the definitions below.

Definition 1. We call $G$ a directed graph if $G = (V, E)$, with $E \subseteq V\times V$.

Definition 2. A directed subgraph of a directed graph $G = (V, E)$ is a directed graph $G' = (V', E')$ such that $V'\subseteq V $ and $E'\subseteq E$.

Definition 3 (!). A path in a directed graph $G$ is a directed subgraph P = (V', E') of G of the form $V' = \{i_0, i_1, ..., i_k\}$, $E' = \{(i_0, i_1), (i_1, i_2), ..., (i_{k-1}, i_k)\}$ with $k\geq 0$. Also, the length of P is defined as $l(P) = |E'|$.

(Note that if $i_0$ is a vertex of $G$, then $(\{i_0\}, \emptyset)$ is a path of length 0 in $G$.)

Question(s). Let $G = (V, E)$ (with $|V| < \infty$) be a directed graph and $l$ be a positive integer. How many paths of length $l$ are there in $G$? Is there any algorithm to compute this number?

share|improve this question
    
You seem to be trying to make a technical distinction between your definition of path and the sequence-of-vertices definition, but I think things need to be a bit more precise to make this distinction. (1) In Definition 2, do you require $E' \subseteq V' \times V'$? (2) In Definition 3, must every point in $V'$ appear in some element of $E'$? (3) May a point $V'$ appear in $E"$ more than once; may an edge $(i,j)$ appear in $E'$ more than once? (As $E'$ appears to be a set of ordered pairs, I assume not.) (4) What are the restrictions, exactly, on $E'$ in Definition 3? –  usul Jul 26 '13 at 2:55
    
@usul (1) I require $G'$ to be a directed graph, so yes. (2) No, not if $k = 0$. (3) Yes, and yes. For instance, if $G = (\{1, 2\}, \{1, 2\}^2)$, then $P = (\{1, 2, 1, 2, 1, 2\}, \{(1, 2), (2, 1), (1, 2), (2, 1), (1, 2)\})$ is a path with $k = 5$ and $l(P) = 2$. Note that $P$ can also be written as $P = (\{1, 2, 1\}, \{(1, 2), (2, 1)\})$, where $k = 2 = l(P)$. However, one can find a path P such that it cannot be written as $P = (\{j_0, j_1, ..., j_{l(P)}\}, \{(j_0, j_1), (j_1, j_2), ..., (j_{l(P)-1}, j_{l(P)})\})$ and this, I think, makes the task of counting these guys hard. –  TuringMachine Jul 27 '13 at 4:37
    
(4) I'll write it more explicitly. Let $G$ be a directed graph. A directed subgraph P = (V', E') of G is a path in G iff there exist $k\in\mathbb{N_0}$ and $i_0, i_1, ..., i_k$ such that $V' = \{i_0, i_1, ..., i_k\}$ and $E' = \{(i_0, i_1), (i_1, i_2), ..., (i_{k-1}, i_k)\}$. –  TuringMachine Jul 27 '13 at 4:44
    
Note that the complexity must depends on $l$, since I can reduce the subset sum problem to this problem. If $O((V+E) \times l)$ is sufficient, then dynamic programming suffice. –  Irvan Dec 13 at 10:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.