Survival Mode

[DjinnKahn]

[Fritzlein]

[DjinnKahn]

Oh, I see. I thought you just wanted a proof that longest path is NP-hard. Going directly from 3SAT is a nice challenge : )

Using only 3 chambers isn't a big problem, since cheating only allows you to use 2 chambers.

[Fritzlein]

[barxool]

[barxool]

[Hippo]

Hmm, I didn't notice I was last on page 4 and discussion continued on page 5 ... I am used to edit last post instead of autoreplaying ... so look at the version on the bottom of page 4 where the authors of the original proof (HC on graph with small degree vertices) was located

BTW: Plesnik proof allows undirecting by adding vertex on outdegree 1 to indegree 1 edges. And if you want cubic graph (all vertices of degree exactly 3) you can add a square with diagonal instead of just one vertex there. So Plesnik's proof is much easier than the original one ([3]).

BTW2: An alternative ... my last step of Tron proof used "fractal corridors as edges" to make all edges (or at least these that are not forced ... (meaninig out deg 2 in deg 2)) same length (forced ones could be longer but not shorter). It would lead probably to simillar scaling as creating big chambers. My resulting map would be graph on grid with maximal degree 3.

P.S.: The book name was probably "Grafové algorítmy" ... Graph algorithms, not Graph Theory I have supposed.

[barxool]

The proof in the .pdf files is about a hamiltonian cycle, but in tron we are interested in an hamiltonian path only.
Moreover it looks like the proof assumes a cubic graphe, and a tron map is not a cubic graph.

If someone has understand Fritzlein's proof, can you post the full map for the following 3SAT expression: (A or B or ~C) and (~A or C or D) ?
that would be great.

[Hippo]

If you know an edge which must be on HC, you can split the edge in the middle adding two dead ends. Or in directed graph you can split a vertex to two veritces one with indegree 0 the other with outdegree 0.

The argument would be more complicated in undirected graphs with all vertices having degree more than 2. There is a construction which trasforms undirected HC to directed as well as the other way. So I would probably use this side step.

The graph is of degrees less than 4 while grid has degree 4 in each vertex. Adding walls you can reduce degrees. You can replace edges by corridors (paths of degree 2 verices) ...