Anarchy in the APSP: Algorithm and Hardness for Incorrect Implementation of Floyd-Warshall

Revision en1, by ko_osaga, 2024-04-15 06:21:59

Hello Codeforces! I just uploaded the first paper of my life to arXiv, and I'm happy to share it with the community, especially because it is very related to competitive programming.

Here is the presentation I gave in MIT Theory Lunch.

What did I solved?

Everyone knows the Floyd-Warshall algorithm for computing the shortest path, it goes like:

rep(k, n) rep(i, n) rep(j, n) A[i][j] = min(A[i][j], A[i][k] + A[k][j]);

And everyone knows this incorrect variant of Floyd-Warshall. I certainly implemented this when I was learning CP, cause I kinda wanted to "fix the loop order".

rep(i, n) rep(j, n) rep(k, n) A[i][j] = min(A[i][j], A[i][k] + A[k][j]);

This is bad, it does not compute the shortest path. It does, however, compute "something". Imagine someone gives you a sparse graph and asks you to compute "something". Then that's actually harder than the correct variant because you can't run Dijkstra! What is this?!

But don't worry, with some observation, you can actually run some sort of Dijkstra:

Theorem 1.2: The "incorrect Floyd-Warshall matrix" can be computed with a single Dijkstra and a simple DP.

Then there's this really funny preprint by DEGwer and EnumerativeCombinatorics which basically says that "nobody cares about loop order cause you can run incorrect ones $$$3$$$ times." This makes total sense when you want to compute the correct matrix in a troll way. But what about the other way around? What if you want to compute the troll matrix, given that you can only use a very serious black box of Floyd-Warshall?

Theorem 1.3: The "incorrect Floyd-Warshall matrix" can be computed with $$$O(\log n)$$$ iteration of Floyd-Warshall plus $$$O(n^2 \log n)$$$ computation.

This is quite interesting if you have a context — it is conjectured that the all-pair shortest path can't be computed faster than $$$O(n^3)$$$ (by Floyd-Warshall) and breaking it will be a major breakthrough. I am basically suggesting one way to do this breakthrough — optimize incorrect Floyd-Warshall XD

Tags solve, more, baekjoon, oj

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en8 English ko_osaga 2024-04-15 09:40:31 213
en7 English ko_osaga 2024-04-15 07:38:25 3 Tiny change: 'afternoon I wanted to' -> 'afternoon we wanted to'
en6 English ko_osaga 2024-04-15 06:45:33 29 Tiny change: ' afternoon, I created' -> ' afternoon I wanted to have some fun, so I created'
en5 English ko_osaga 2024-04-15 06:44:37 19 Tiny change: 'as in NYC (cuz I like there) and was s' -> 'as in NYC and was s'
en4 English ko_osaga 2024-04-15 06:43:47 0 (published)
en3 English ko_osaga 2024-04-15 06:43:32 98 (saved to drafts)
en2 English ko_osaga 2024-04-15 06:42:30 1560 Tiny change: 'ppened??\nOk, in late Jan' -> 'ppened??\nIn late Jan' (published)
en1 English ko_osaga 2024-04-15 06:21:59 2378 Initial revision (saved to drafts)