Tag Info

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

3

There are several such algorithms for various graph problems; for Hamiltonian path one example is due to Björklund [1]. These algorithms are often algebraic and the "random element" stems from the application of the Schwartz–Zippel lemma. Usually, the algorithms work so that the graph property we are interested in is somehow represented as a (multivariate) ...

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

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

This is the longest path problem. It's NP-hard to find the longest path in a general graph. You can try applying any standard algorithm for finding longest paths. Search on this site for "longest path" and "Hamiltonian path" to find many references. Since you're willing to accept suboptimal solutions, you might look for a heuristic or approximation ...

2

The distance $d_G(u,v)$ between two disconnected vertices $u,v$ of a graph is usually defined as $+\infty$. As a consequence the diameter of a disconnected graph $G=(V,E)$ is $$\textrm{diam}(G) = \max_{u,v \in V} d_G(u,v) = + \infty.$$

2

If the vertex $u$ is not added to to $G'$, then a Hamiltonian cycle in $G'$ does not necessarily correspond to a Hamiltonian path from $s$ to $t$. This is because the cycle may not have $s, t$ adjacent to each other. For example, one could have Since there is no Hamiltonian path from $s$ to $t$ in the first graph, there is no Hamiltonian cycle in the second ...

1

Hint: Suppose that $G$ already had a Hamiltonian cycle, but no Hamiltonian path from $s$ to $t$. OK, this clearly needs more explanation. Consider the case of an undirected cycle graph with 4 vertices. This graph, $G$, has a Hamiltonian cycle, but it does not have a Hamiltonian path from $0$ to $2$. Now add an edge $(2,0)$, to obtain a new graph, $G'$. This ...

1

I ended up using the UCT (MCTS with UCB1) algorithm but with a twist. Normally, in UCT, the simulation phase is a simulated play-through of a game with moves chosen at random. If the simulated game ends in a win, the node's score, from where the simulation was played out, and all it's parents' scores all the way back to the root, are incremented by 1. In ...

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

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