4

The problem of finding a Hamiltonian path in a partial grid graph (that is, an arbitrary subgraph of a grid, not necessarily even induced) remains NP-complete [1]. Thus, you are likely out of luck for a polynomial-time approach. A good choice for a heuristic might depend on your instance size and further structure. However, in general, you could try say a ...


2

Yes it exists and the existence of a linear ordering not only shows the existence of the topological oredering over the vertices but also that this ordering is unique. It is not hard to prove that the graph represents a linear ordering using the facts that the graph is complete and acyclic. That should be a good exercise for you (proving a relation is a ...


2

The class of graphs that contain a Hamiltonian cycle is known as Hamiltonian graphs. Being Hamiltonian doesn't really imply much: a wide range of well-known graph parameters (diameter, treewidth, chromatic number, ...) can still be unbounded. At least partly, this is the reason there aren't many non-trivial subclasses of Hamiltonian graphs known. As an ...


2

Your problem is a variant of Euclidean TSP in which you are looking for a path instead of a cycle. You can (essentially) reduce your problem to the usual Euclidean TSP by adding a point at infinity. Here is a quick summary of what is known about Euclidean TSP, paraphrasing a survey of Czumaj from the Encylopedia of Algorithms: For every fixed $k$, there is ...


2

Problem 1 can be solved in polynomial time. Here is a simple algorithm to compute it in $O(n^2 + nm)$ (it can probably be done faster). This can be solved in a dynamic programming style. If we find the shortest length $k$ path to all nodes from source $s$, then we can easily find the shortest length $k+1$ path to all nodes from source $s$. Let $d_k(v)$ be ...


2

Actually, grid graphs are a very specific class of input problems, and a good number of algorithms are known that can solve problems which remain hard in other instances, i.e., non-grid graphs. Even if it is not directly related to your question, I could not avoid citing the following paper: F. Keshavarz-Kohjerdi, A. Bagheri, A. Asgharian-Sardroud. A ...


2

You are right that in the coding of the graph one needs a possibly quadratic number of strands to represent the edges. My guess is that Adleman likes to distinguish the two kinds of operations. First there is the coding of the input graph, which may be very complicated to avoid accidental combinations. Then there is the number of laboratory steps to ...


1

Let $P$ be an arbitrary simple path in the graph. If $P$ appears in a Hamiltonian cycle of the graph, you can remove all the vertices of $p$ except the first and the last vertex, connect these two vertices with an edge and the resulting graph must be Hamiltonian. Keeping this in mind, we can build the Hamiltonian cycle step by step starting with path of ...


1

One simple way is to face this problem like a state-space search. Assume that going in each of 4 directions on a node that has not been visited is one action. Make a function that is responsible for producing all the next possible states given the current state. It produces a list of all next actions (at most 4 states). As you may know, we call this function ...


1

Here is what it boils down to. There are $n$ vertices $v_1,\ldots,v_{n-1},v$. For each $i$, there is an edge either from $v$ to $v_i$ or from $v_i$ to $v$. We need to show that one of the following holds: There is an edge from $v$ to $v_1$. There is $i < n-1$ such that there are edges from $v_i$ to $v$ and from $v$ to $v_{i+1}$. There is an edge from $v_{...


1

I'm not able to understand how having a cycle makes it solvable? The basic intuition is that it reduces the amount of state you need to track. With cycles allowed you just need to build up a table of the shortest length-k path from s to each other vertex. With cycles disallowed you need to track all of the intermediate vertices, so you potentially wind up ...


1

This answer shows this problem is NP-hard. Further research is needed to determine whether it belongs to APX or it is APX-hard. Let $G$ be a complete directed acyclic graph, i.e., you can name the vertices $1,2,\ldots,n$ and there is an edge $(i,j)$ for all $i<j$. Let $D'=D$, and $k$ is equal to half of the sum of the weights of all vertices. Now there ...


1

Hamiltonian path problem remains NP-complete in planar graphs [1], so your problem is also NP-complete since in a planar graph, two edges cannot intersect with each other. [1] Garey, M. R., Johnson, D. S., & Tarjan, R. E. (1976). The planar Hamiltonian circuit problem is NP-complete. SIAM Journal on Computing, 5(4), 704-714.


Only top voted, non community-wiki answers of a minimum length are eligible