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.

Let $G=(V,E)$ denote a digraph, $s,t\in V$ two different vertices in $G$ and $w:E\to\mathbb R$ the weighting function for all edges. Moreover $\mathcal K$ denotes the set of all walks, $\mathcal E$ the set of all trails and $\mathcal W$ the set of all simple paths from $s$ to $t$ in $G$. $\varphi$ is the resulting function of the problem to find a minimal walk, trail or simple path. Prove the following statements:

  1. The minimum of $\varphi$ over $\mathcal E$ and the mimium of $\varphi$ over $\mathcal W$ only exist iff $\mathcal W\neq \emptyset$.
  2. The minimum of $\varphi$ over $\mathcal K$ exists iff $\mathcal K\neq\emptyset$ and for each walk $K\in\mathcal K$ no node $v_i$ in $K=(s,e_1,v_1,\ldots,e_p,t)$, with $v_k\in V,e_k\in E$, is part of a closed walk with negative length.
  3. If there exists a minimum of $\varphi$ over $\mathcal K$ then there exists a simple path $W$ from $s$ to $t$ with at most the same minimal length.
  4. With $\mathcal K\neq\emptyset$ and $w(e)>0$ for each $e\in E$ then each minimal walk from $s$ to $t$ is a simple path.

I did come up with possible solutions for 1., 2. and 4. yet I need some help to understand 3. and I would appreciate any suggestion for the other solutions so far.


  1. Assume that $\mathcal W=\emptyset$, therefore there is no simple path $w=(s,e_1,v_1,\ldots,e_p,t)\in\mathcal W$ with disjoint vertices $v_k$ and disjoint edges $e_k$. Our search for shortest paths and walks will yield an empty result as there is nothing to minimize when the two vertices $s$ and $t$ aren't connected. We recognize $\mathcal W\neq\emptyset$ so that we are able to find at least one shortest path or walk which can be minimized under all circumstances. Even if it contains a closed walk with a negative length, we are only able to go through it at most once, otherwise some edges/nodes would be visited more than once in constrast to the assumption, that $w\in\mathcal W$ is a simple path. The same applies for $\widetilde w=(s,e_1,v_1,\ldots,e_p,t)\in\mathcal E$ where all edges $e_k$ are disjoint. If there is no simple path, then we get again an empty result which can't be minimized and the assumption $\mathcal W=\emptyset$ is once again wrong. Though we can visit any vertex more than once, the number of edges in all possible trails in $\mathcal E$ has an upper bound of $|E|$ and therefore there must exist a minimal trail between $s$ and $t$.
  2. Let's assume that $\mathcal K=\emptyset$. We know that $s$ and $t$ aren't connected by any walk, trail or simple path and are in two different components of $G$. This implies that we cannot minimize $\varphi$ over $\mathcal K$ if there are no results to chose from and once again $\mathcal K\neq\emptyset$ must be true. With this assumption we do look at what happens if the graph has a closed walk with negative length and assume that there still exists a minimum. Without loss of generality we can collapse all nodes $v_k$ in one "supernode" which we call $v$. Now we do look at a graph $$G'=\left(V'=\{s,v,t\}, E'=\{e_1=(s,v),c=(v,v),e_2=(v,t)\}\right).$$ The closed walk in this example is $C=(v,c,v)$ with $w(C)<0$. If we are to minimize $\varphi$ over $\mathcal K$ we are allowed to visit both vertices and edges as often as possible. Therefore $\varphi(G')=w(e_1)+w(e_2)+w(c)\cdot k$ where $k$ denotes the number how many times we go through our negative walk. Apparently we can do so infinitely and each time we can not minimize. This is contradicting our assumption that such a minimum would exist and therefore there cannot be such a closed walk with negative length.
  3. ???
  4. We select an arbitrary $K=(s,e_1,v_1,e_1,v_1,e_1,v_1,e_2,v_2,\ldots,e_p,t)\in\mathcal K$ and do want to minimize this over $\mathcal E$. The combination $C=(v_1,e_1,v_1)$ does repeat and would not be simplyfied to $C'=(v_1)$ by the algorithm if $w(C)=w(e_1)\leq 0$, however we know that $w(e)>0$ for each $e\in E$. Therefore we know that no closed walks $C$ with $w(C)\leq 0$ can exist and that $K\in\mathcal E$. Assuming $K\not\in\mathcal W$ we can again apply the concept of a "supernode" and without loss of generality we do analyze $K=(s,e_1,v,e_2,u,e_3,v,e_4,t)$. With the precondition that $w(e_2)+w(e_3)>0$ the cycle $C=(v,e_2,u,e_3,v)$ could be replaced by $C'=(v)$ to minimize $\varphi$ over $\mathcal W$. We know that there is no $e\in E$ such that $w(e)=0$ and therefore there is no possibility that we have a cycle in our shortest simple path implying that each edge and each vertex is visited at most once, thus $K\in\mathcal W$ being a shortest simple path.
share|improve this question
add comment

1 Answer 1

3. In this question you can use the process of reduction from a walk to a simple path.

Let $K = (s,e_1,v_1,e_2,v_2,...,e_p,t)$ be the minimum of $\varphi$ over $\mathcal K$ and suppose $K \notin \mathcal W $, thus there are $v_i$ and $v_j$ in $K$ with $i \ne j$ but $v_i=v_j$. Thus, you have a closed walk inside $K$, but from your answer of item 2, this closed walk need have lenght nonnegative, so it can be removed from $K$, producing a new walk $K'$ with value not worse (in fact, the value must be equal, because we selected K the minimum of $\varphi$). By induction on the number of repeated vertices in the walk, we will get a simple path with at most the same minimal length.

share|improve this answer
add comment

Your Answer

 
discard

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

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