Timeline for Frog game on tree graphs is in NP but not in P (NP-complete)?
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 18, 2022 at 17:09 | comment | added | Vepir | @StevenStadnicki Well it is an open problem, but I agree, thanks for the comment. | |
| Oct 18, 2022 at 17:02 | history | edited | Vepir | CC BY-SA 4.0 |
further clarification
|
| Oct 18, 2022 at 16:53 | comment | added | Vepir | @PeterTaylor I've checked again, it seems your definition is more common when talking about simple graphs, and mine when talking about multigraphs, but I've seen it used vice versa. Maybe it is best to just specify $V,E$. | |
| Oct 18, 2022 at 16:46 | comment | added | Peter Taylor | The standard I'm used to from the literature is $G = (V, E)$ where $E$ is a set of unordered or ordered pairs according to whether the graph is undirected or directed. | |
| Oct 18, 2022 at 16:34 | comment | added | Steven Stadnicki | You might want 'NP complete' — there are after all no problems known to be in NP and not in P... | |
| Oct 18, 2022 at 15:42 | history | edited | Vepir | CC BY-SA 4.0 |
clarifications
|
| Oct 18, 2022 at 15:37 | comment | added | Vepir | @PeterTaylor Ah yes sorry, I meant to ask that (In NP and not in P). | |
| Oct 18, 2022 at 15:35 | comment | added | Vepir | @PeterTaylor It is the incidence function, mapping every edge to an unordered pair of vertices (that is, an edge is associated with two distinct vertices). Is that not the standard way to define graphs? Using sets of edges and vertices, and a function that relates them. | |
| Oct 18, 2022 at 15:31 | history | edited | Vepir | CC BY-SA 4.0 |
added 8 characters in body; edited title
|
| Oct 18, 2022 at 14:05 | comment | added | Peter Taylor | Also, the question itself is trivial: the sequence of $f_k$ is a certificate which can be verified in polynomial time. Perhaps the question is intended to be whether the problem is in P? | |
| Oct 18, 2022 at 14:02 | comment | added | Peter Taylor | What is $\phi$? I thought that it was a vertex weighting function and that $f(v_1)$ was a typo for $\phi(v_1)$ until I looked at the linked examples and realised that $f(v_1)$ is a typo for $f_k(v_1)$. | |
| Oct 18, 2022 at 13:06 | comment | added | Vepir | @AlekseiKulikov You misunderstood the rules. For example, a star graph is not solvable in leaf vertices if it has $3$ or more leaves. The $f$ frogs must jump exactly over $f$ edges, and can't jump to empty vertices (with no frogs). | |
| Oct 18, 2022 at 12:59 | comment | added | Aleksei Kulikov | I am slightly confused and maybe misunderstood the problem, but isn’t the frog game winnable for any vertex of any tree (and a fortiori any connected graph by passing to a spanning tree): just put a root at this vertex and start moving frogs from the bottom level up. All this is doable in polynomial (maybe even linear) time. | |
| Oct 18, 2022 at 12:27 | history | asked | Vepir | CC BY-SA 4.0 |