HN Explorer

Ask HN: Are new graph algorithms still being devised?

12 points by jaxk ↗ HN
Just wondering if there are graph algorithms beyond the textbook ones that are still being designed/devised? This post [1] from a few days back prompted this question.

[1] https://news.ycombinator.com/item?id=27294401

5 comments

[ 2.9 ms ] story [ 23.8 ms ] thread
duped
All the time! Often you'll need to come up with a modification or variant of a textbook algorithm for particular applications.

For example, node-based editors in game engines and other media software need a few key algorithms, but the ordering of incoming/outgoing edges have meaningful semantics that might need to be considered.

You may need to use a custom algorithm to write a solver for a particular problem, for example latency/delay compensation in various networks (audio, distributed sensors, etc).

Other times you may want to combine multiple algorithms into single traversals, which is often used in single-pass compilers or parsers. These can be tricky if the traversal modifies the graph.

Then there are hypergraphs, which are so generic you probably need to treat your application as a special case.

jaxk
Yeah I get that you have to tweak canonical algorithms to suit the current problem but I am thinking more about developing algo for open problems or improving the performance at research level. Also, are algorithms beyond basic ones like shortest path, a* search and network flow are ever needed in real world situations? They all seem done and dusted pretty much.
duped
Yes graph algorithms are actively researched. You can browse arxiv.org and see plenty of recent submissions: https://arxiv.org/search/?query=Graph&source=header&searchty...

For applications, compilers need graph coloring. Task schedulers need graph cuts. Since these are NP complete there is plenty of room for research on specific implementations with various heuristics.

yun111
I wrote a paper detailing one last month, and conjectured that a different approach would work as well. I believe that other researchers are close to proving my conjecture. So yes.
high_byte
adding to what others said: graph based neural networks is a hot topic and I believe is the next major breakthroughs in AI.