3 ms·
The following open research problem. Given an undirected graph G with two vertices s and t, the task is to determine whether there is an undirected path connect
by a3_nm 3y ago
The following open research problem. Given an undirected graph G with two vertices s and t, the task is to determine whether there is an undirected path connecting s and t which is simple (no repeated vertices) and has length divisible by 3.
It is not known whether this problem is NP-hard, or whether it can be solved in polynomial time; apparently the question is open since the early 90s.
(The problem is also open for paths of length p mod q for any fixed p and q (fixed means they are constants, and are not given as input), whenever q>2. The problem is known to be in PTIME for 0 mod 2 and 1 mod 2, and to be NP-hard when the graph is directed. Pointers to related work here: https://gitlab.com/a3nm/modpath https://gitlab.com/a3nm/modpath)
- sdenton4 3y agoAn old favorite open graph theory problem: In your right hand, take any collection of trees with 2, 3, ..., n vertices. These have a total of 1+2+...+n-1 edges, ie, n choose 2. In your left hand, take the complete graph with n vertices. This, of course, has the same number of edges. Conjecture: it is always possible to pack/embed the trees into the complete graph in such a way that all edges are matched exactly once. The problem has been open for like fifty years, lacking a counter-example or a proof. One can assume Erdos thought hard about it at some point...
- a3_nm 3y agoInteresting! It looks like this is called the "Gyárfás tree packing conjecture".
- muldvarp 3y agoWhat's the motivation for this problem if there is any? It's a really specific problem.
- a3_nm 3y agoThis came from a database theory study about queries on graphs: https://dl.acm.org/doi/10.1145/3517804.3524149 https://dl.acm.org/doi/10.1145/3517804.3524149 for the paywalled version, https://www.theoinf.uni-bayreuth.de/pool/documents/Paper2021-25/Paper2022/rpqs-undirected-graphs.pdf https://www.theoinf.uni-bayreuth.de/pool/documents/Paper2021... for the open-access paper. But honestly I find the problem intriguing for its own sake.
- fuzzer371 3y agoI mean, so what if there is?
- 4death4 3y agoWhat makes it NP-hard? Naively, I would assume the number of simple paths between any two nodes in a graph to a polynomial function of the number of nodes plus the number of edges, so checking every path wouldn't be hard.
- melvinmelih 3y agodone: https://chat.openai.com/share/c8bc7305-6c75-4194-8753-b319d67ae12b https://chat.openai.com/share/c8bc7305-6c75-4194-8753-b319d6...
- a3_nm 3y agoYes, ChatGPT is really bad at those things...
- voxl 3y agoI can't tell if you're making a joke, a troll, or genuinely believe what ChatGPT tells you with out bothering to test it. This is why I hate the AI hype, because people do legitimately do this and think "wow it's so smart." When I explained the halting problem using Python to a student he asked "did you use ChatGPT?" No. Of course not...
- melvinmelih 3y agoLol it was a joke, but I imagine it won’t take too long before AI can start solving problems that we’ve been struggling with as humanity.