Timeline for Blind construction of planar graph with additive spanning tree count
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 14, 2022 at 13:12 | comment | added | Turbo | @JukkaKohonen there may be other tricks to reduce to polynomial size. The point of the problem is not to compute P1 and P2 ahead of time. I need a blind construction. | |
| Feb 14, 2022 at 12:59 | comment | added | Jukka Kohonen | It's true that you can compute $P_1$ and $P_2$ in polynomial time (polynomial of the size of the input graphs) and then you can make the cycle graph of length $P_1+P_2$. But that cycle graph can be exponentially large (with respect to input size). So I don't think this solution qualifies as "a graph construction in polynomial time", at least if you require an explicit output of the constructed graph. | |
| Feb 12, 2022 at 23:41 | comment | added | Turbo | Yeah technically speaking I want to be in Logspace but since I am talking to mathematicians I figured some amount of difficulty becomes evident with the way I am portraying (there is no known logspace or even non-deterministic logspace (both are conjectured to be same) algorithm to find $P_1$ or $P_2$). | |
| Feb 12, 2022 at 23:40 | history | edited | Turbo | CC BY-SA 4.0 |
added 23 characters in body
|
| Feb 12, 2022 at 23:40 | comment | added | Sam Hopkins | The other "moral" problem with your question is that we can simply compute the numbers $P_1$ and $P_2$ in polynomial time. | |
| Feb 12, 2022 at 23:39 | comment | added | Turbo | I think that morally answers my question. | |
| Feb 12, 2022 at 23:39 | comment | added | Sam Hopkins | Well, you get every number greater than 2 by considering the cycle graphs. | |
| Feb 12, 2022 at 23:33 | comment | added | Sam Hopkins | There is no simple graph (planar or otherwise) with exactly 2 spanning trees, right? | |
| Feb 12, 2022 at 23:28 | history | asked | Turbo | CC BY-SA 4.0 |