1
$\begingroup$

EDIT Dec 14th 2010
The algorithm is not correct: it's not the case that it always returns the optimal $W$.


While reasoning on this and other similar questions, I've sketched an algorithm that, given an undirect weighted graph $G=(V,E)$ of $n$ vertices and a vertex $v_i \in V$, returns an array $W$ of $n$ weights, where each $W_j$ (with $j \in [1,n]$) is the weight of the path of maximum weight from $v_i$ to $v_j$. Something must be wrong with the algorithm, but so far I couldn't figure out what. The algorithm seems correct at first sight, maybe its flaw is that the labeled tree $T$ it builds (see below) grows exponentially in size (I didn't yet implement it to see what happens).

Other than its input, the algorithm uses two further objects:

  1. A labeled tree $T$, which is initially composed by only one node whose label is $i$ (such node will be $T$'s root)
  2. A relation $R \subseteq D^2$. $D$ is the domain of "paths without repetition", and $R(x,y)$ means "path $x$ removes path $y$". $R$ is initially the empty set.
  3. A relation $Q \subseteq D^2$. $Q$ is built from $R$. $Q$ is initially the empty set.

The algorithm operates as follows:

  1. For each leaf $v_k$ of $T$, add to it one new child node labeled $c$ for each $v_c \in V$ such that $\{ v_k, v_c \} \in E$ and there isn't any node labeled $c$ in the path in $T$ from $v_k$ to the root.
  2. If $T$ changed during Step 1, go to Step 3. Else, go to Step 7.
  3. Given a generic node $v_t$ of $T$, let $p_t$ be the path in $T$ from the root to $v_t$, let $w_t$ be the weight of $p_t$, and let $l_t$ be the label of $v_t$. Let $V(l)$ be the set of nodes of $T$ whose label is $l$. Now for each different label $l_k$ appearing in a leaf of $T$, let $V_2(l_k)$ be the set of all those subsets of $V(l_k)$ having cardinality $2$; for each $\{v_{k_1}, v_{k_2}\} \in V_2(l_k)$, if $w_{k_1} \geq w_{k_2}$ then add $(p_{k_1}, p_{k_2})$ to $R$, else add $(p_{k_2}, p_{k_1})$ to $R$.
  4. Compute the relation $Q$ as follows: $Q$ contains all the couples of $R$, plus those obtained according to the following rule: if $(x, y) \in Q$ and $(z, w) \in Q$ and $y$ is a prefix of $z$, then $(x, w) \in Q$.
  5. For each $y$ such that $\exists x (x, y) \in Q$, if $\not \exists z (z, y) \in Q$ such that $y$ is a prefix of $z$, then remove from $T$ the subtree whose root $r$ has a path from $T$'s root to $r$ equal to $y$.
  6. Set both $R$ and $Q$ equal to the empty set. If $T$ changed during Step 5, then go to Step 3. Else, go to Step 1.
  7. Set $W_j = 0, \forall j \in [1,n]$. Visit the tree $T$: for each visited $v_t$, if $w_t > W_{l_t}$, set $W_{l_t} = w_t$. Return $W$.

Question(s)

  1. Is the algorithm correct?
  2. Where is it flawed?
  3. Is there an instance such that $T$ has exponentially many leaves?

Apologies in advance if this algorithm turns out to be completely uninteresting and naive.

$\endgroup$
  • 1
    $\begingroup$ I do not think that it is appropriate on this site to describe an algorithm and ask others to check its correctness. Specifically, I am afraid of other people starting to post similar “I may have found a poly-time algorithm for an NP-complete problem, please point out its error” questions. Voted to close as off topic. $\endgroup$ – Tsuyoshi Ito Dec 15 '10 at 23:16
  • $\begingroup$ I agree with Tsuyoshi on this one. Walter, maybe a discussion on meta would clarify whether such questions are appropriate. $\endgroup$ – Suresh Venkat Dec 16 '10 at 8:51
  • $\begingroup$ I do not know what kind of research you guys do, but this seems to be a typical question that can come up. If we forbid low-level as well as this type of question, all we are left with is asking for references and big-picture. $\endgroup$ – Raphael Dec 16 '10 at 10:02
  • $\begingroup$ @Raphael: Even if it is typical to come up with a “proof” of P=NP, I believe that asking others to check its correctness is inappropriate here. And I hope that your assertion that “If we forbid low-level as well as this type of question, all we are left with is asking for references and big-picture” is false. If it were true, that would only mean that this site is not interesting (at least to me). $\endgroup$ – Tsuyoshi Ito Dec 16 '10 at 13:18
  • $\begingroup$ I posted a policy proposal related to this question on Meta. $\endgroup$ – Tsuyoshi Ito Dec 16 '10 at 13:20
1
$\begingroup$

Two questions where I think you have remained unclear:

  • Are there any assumptions on the weight function?
  • What exactly holds if $(x, y) \in R$?

Ad 4: You break your desired invariant for $R$ here since the last node in $x$ does not necessarily occur in $w$ at all. Example: $x = abc, y=adc, z=adce, w=ae$

I believe a worst-case instance might be the complete graph with $w(i,k) = 1$ for $i$ the starting node and all $k\neq i$, and $w(j, k) = 0$ for all $j,k \neq i$. Paths with more nodes will never remove those from earlier iterations so the tree is never shrunk at all, growing up to having $n!$ nodes.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @Raphael: Initially, I felt that weights must be non-negative in order for the algorithm to work, but now I'm suspecting that it's not necessary. However, for simplicity let's assume that the weights are non-negative. $\endgroup$ – Giorgio Camerani Dec 10 '10 at 11:43
  • $\begingroup$ @Raphael: $(x,y) \in R$ means that the last node in path $x$ is reached with an overall cost which is higher than the overall cost used to reach the same last node in path $y$. So $x$ has to be preferred, since it's more costly. $\endgroup$ – Giorgio Camerani Dec 10 '10 at 11:49
  • $\begingroup$ @Raphael: I've edited the question a bit: $p_t$ is the path from $T$'s root to $v_t$, not from $v_t$ to $T$'s root (as previously stated). I'm reasoning on the further parts of your answer. $\endgroup$ – Giorgio Camerani Dec 10 '10 at 11:57
  • $\begingroup$ Ok, please see updated comment regarding step 4 above. $\endgroup$ – Raphael Dec 10 '10 at 12:08
  • $\begingroup$ @Raphael: Yes you're right, I had exactly the same thought while I was at launch. The problem is that the term "transitive closure" is inappropriate for $R'$. Let's say instead that we build a new relation $Q$ from $R$, where $Q$ has nothing to do with the transitive closure of $R$. $Q$ contains $R$, plus those couples obtained through the above rule. Note: $Q$ is needed for correctness, since it avoids eliminating subtrees that must not be eliminated (because their elimination can lead to a non-optimal $W$). $\endgroup$ – Giorgio Camerani Dec 10 '10 at 13:19

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