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$

closed as off topic by Tsuyoshi Ito, Suresh Venkat Dec 16 '10 at 8:52

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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.

$\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.