Both algorithms make sense for undirected graphs as well: we can view K_n as directed graph by doubling each edge. But unlike Bellman-Ford, Dijkstra does not construct a DAG -- he rather solves the recurrence via successive approximation of distances. On NP vs P/poly via monotone circuits: this could interest you.

very interesting! close to my own ideas. will dig into it. surprised theres not much word about it so far. how did you hear about it? reminds me of the Deolalikar proof from a few yrs ago which caused a lot of commotion at the time. this overall approach is already immed more conventional/credible....

you say in your writeup "If the answer is YES, this would show that the Bellman-Ford is optimal in a wide class of DP algorithms." what wide class are you talking about? doesnt seem clear...

it occurs to me that maybe there are prob papers that try to prove how "optimal" bellman-ford is ... have you looked in that direction? if you wrote this up as a proof, what papers would you cite if any?

starting with something simpler: is it true that one can just start with K_n and enumerate all s-t paths in K_n? is there some other simpler way to characterize this set? wondering, what is a rough estimate of the number of these paths?

also it occurs to me that for each K_n "represented" by a DAG, there would probably be a minimal size DAG that represents K_n, true? does it make sense to focus only on the minimal size DAG and not others?

oops! see you are focusing on the smallest DAG...

think you should name the smallest representing DAG somehow with notation.

my instinct is to study problems like this empirically esp for problems that are "small" in growth eg polynomial. acc to your writeup one should be able to list out minimal G_n and they only grow in size O(n^3)... how hard would it be to write code that finds those G_n? do you have grad students lying around that can work on this? thats what steven hawking does, wink =)

guess there is a set of minimal DAGs for each "n"...?

re enumerating paths of K_n. isnt it just a list of permutations of subsets of vertices?

I am trying to reply in a row. He submitted the paper to a journal, so we'll see. (I had no time to check the details, have had only some general comments, as why Razborov fails and he not.)

Bellman-ford DP algorithm is "incremental" (see, e.g. here. If YES, it would be optimal in this class.

What papers to I'd cite: one of them is Kerr 1976 showing that the Floyd-Warschal DP algorithm for the all-pairs shortest paths is optimal if only Min and Plus operations are used.

The number of all simple s-t paths in K_n is easy to give: it is about the sum over all $k\in [n]$ of $n!/(n-k)!$.

Of course, we can assume that the DAG is minimal.

Empirical approach may be too boring. Things here may be easier. Say, it is enough to show that paths in DAG representing the paths in $K_n$ with $k$ edges cannot meet too often, for otherwise we could force a path in DAG whose labels do not contain an s-t path.

P.S. To my last comment: Stop all paths in DAG representing the s-t paths of length k after their i-th mark (i<k), and show that there must be about n *distinct" "stopping nodes in DAG. Then the DAG must have about n^2 nodes, and about n^3 edges. Cases k=1,2 are easy. We "only" need to get rid with larger k's.

- "had had only some general comments, as why Razborov fails and he not".. can you elaborate on that

- thx for link to your recent paper, helps a lot to explain the bkg

- do you ever read rj lipton blog? his coverage of looking at the polytope associated with travelling salesman problem reminds me of your directions

- it seems you are looking at a mapping between permutations-of-subsets and paths-on-DAGs. in my mind it is easier to talk about permutations-of-subsets than K_n.

- empirical research is useful to check conjectures/intuition for finite cases of n, sometimes for "moderate size" n, or occasionally higher

On Juni's paper: it's difficult to elaborate. Let's wait for the paper. Lipton's blog is great. But polytopes for TSP question is much, much harder. Yes, permutations (of various lengths) is a right modell for s-t paths. Empirical: even if we only have O(n^3) edges, there may be exp(n^3) DAGs to consider.

On Jun's paper again: he also uses a kind of "approximation" (with refined Sunflower Lemma). But Razborov here shows that no argument based on approximating the gates will work for general circuits. This was my biggest trouble.

- looked for links on google to jun's paper but there seem to be none so far. do you know his bkg? the approach is plausible but his style seems "different" .. maybe nonacademic .. has he written any other papers? seems not so far ..

- razborovs impossibility proof of approximation for general circuits. have heard that cited before in obscure places. have you read it?

- it appears you are looking into a sort of DAG-based "compression algorithm" for permutations-of-subsets...

- maybe unf for JF has the same name as famous japanese voice actor...?! surely not the same guy... it might interfere somwhat with him getting his paper taken seriously...

- found his paper "hamming distance between two uniform set systems". says hes in dept math/CS at Indiana State University, Terre Haute, IN. but going to their web site & searching on his last name in directory leads to no result...?

looks like this might be him on linkedin. says was last teaching at Indiana State U in 2006

- how did you find/hear about his page?

- dont you think the DAGs that satisfy the representation are not so big? any ideas on how big?

- think he disabled comments on his blog...

- ok! figured out how to comment. put a comment. am following him on my blog.

- "wait for the paper". huh? the paper(s) are already on his web site. its enough to evaluate everything. doubt that a submitted version would be much different.... and wouldnt he have just submitted exactly what is on his site? how do you know he's submitted it? any idea which journal?

- if razborovs argument against approximations was persuasive/broad, figure you would have included it in your book...!

consider the simple DAG with verticies u_n and labels e_n, u_1(e_1)->u_2(e_2)->u_3(e_3)->...->u_n(e_n) using your own notation. doesnt this represent K_n under the definitions?

nevermind I see now it doesnt.

but still think it might be helpful to describe/exhibit the small examples or some small examples for small n, can they be constructed? what do they look like etc