undefined | Better HN

0 pointsa3_nm2y ago0 comments

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)

0 comments

sdenton42y ago

An 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_nmOP2y ago

Interesting! It looks like this is called the "Gyárfás tree packing conjecture".

muldvarp2y ago

What's the motivation for this problem if there is any? It's a really specific problem.

a3_nmOP2y ago

This came from a database theory study about queries on graphs: https://dl.acm.org/doi/10.1145/3517804.3524149 for the paywalled version, 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.

4death42y ago

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

penteract2y ago

In the complete graph on n vertices, there are (n-2)! simple paths of length n-1 between any pair of distinct vertices, which is more than any polynomial in the number of vertices or edges.

3np2y ago

> What makes it NP-hard?

That's the question, isn't it?

fuzzer3712y ago

I mean, so what if there is?

melvinmelih2y ago

done: https://chat.openai.com/share/c8bc7305-6c75-4194-8753-b319d6...

voxl2y ago

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

melvinmelih2y ago

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

a3_nmOP2y ago

Yes, ChatGPT is really bad at those things...

j / k navigate · click thread line to collapse

0 pointsa3_nm2y ago0 comments

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.

0 comments

sdenton42y ago

An 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_nmOP2y ago

Interesting! It looks like this is called the "Gyárfás tree packing conjecture".

muldvarp2y ago

What's the motivation for this problem if there is any? It's a really specific problem.

a3_nmOP2y ago

4death42y ago

penteract2y ago

In the complete graph on n vertices, there are (n-2)! simple paths of length n-1 between any pair of distinct vertices, which is more than any polynomial in the number of vertices or edges.

3np2y ago

> What makes it NP-hard?

That's the question, isn't it?

fuzzer3712y ago

I mean, so what if there is?

melvinmelih2y ago

done: https://chat.openai.com/share/c8bc7305-6c75-4194-8753-b319d6...

voxl2y ago

I can't tell if you're making a joke, a troll, or genuinely believe what ChatGPT tells you with out bothering to test it.

melvinmelih2y ago

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

a3_nmOP2y ago

Yes, ChatGPT is really bad at those things...

j / k navigate · click thread line to collapse