6

The simplest solution is the one suggested by Yuval Filmus. That is, take a simple path on $n$ vertices, and finish the construction after you have added some number of edges. Clearly, it is easy to enforce the maximum degree condition as well. Alternatively, you could generate graphs whose structure guarantees the existence of a Hamiltonian path. For ...


6

Overview of the problem If you takes teenagers as vertices of a graph, and have an edge whenever the two teenagers are compatible. This gives you an undirected graph, and what you need is a Hamiltonian path in this graph (a path that contains every node exactly once). Maybe searching the web on this abstract version of the problem will yield more ...


5

The idea of the backtracking algorithm is simple, though somewhat cumbersome to express. Perhaps it's easiest to explain it working through the example in the question. We start by putting $T_1$ on chair 1. We then put $T_2$ on chair 2. Then we put $T_3$ on chair 3, and we discover a conflict. So we backtrack, replacing $T_3$ with the next available student. ...


4

The solution suggested by Juho applies to any problem where you can generate an object that trivially has the property you're interested in and then modify it in a way that maintains that property: For the problem in the question, start with a path and randomly add edges obeying the degree conditions. To generate a graph with a $k$-clique, start with a $k$-...


4

It seems that you're trying to construct the graph $K_{37}$ from string and nails without cutting the string. For this, you don't want a Hamiltonian path (a path that visits every vertex exactly once) but an Euler trail (a walk that visits every edge exactly once). In the case of a complete graph, finding an Euler trail is trivial: start at any vertex and ...


4

Yes it is NP-complete. Membership in NP is trivial. Thus, we must only show NP-hardness. To do so, we use a reduction from the original Hamilton cycle problem. Given a graph $G=(\{v_1,\dots,v_n\},E)$, we can construct a new Graph $G'=(\{v_1,\dots,v_n\}\cup\{v_1',\dots,v_n'\},E \cup \{(v_i,v_i')\mid 1\leq i\leq n\} \cup \{(v_i',v_i)\mid 1\leq i\leq n\})$. ...


4

You can reduce to a normal TSP variant by adding a dummy city that is distance $0$ away from each of the existing cities. (See also this answer on StackOverflow.) Edit: it seems that my suggested modification is not quite appropriate: as I understand it, your Hamiltonian path has a fixed starting point but no fixed end point. One way to solve this is to add ...


4

This graph is known as a de Bruijn graph, and its Hamiltonian circuits are known as de Bruijn sequences. Both are well understood (for example, we know exactly how many of these exist).


4

I don't understand how the reduction from FACT to 3-SAT works. Are there any simple articles in which I can read about it? Most of the reading material assumes several steps of knowledge. First, you should read about how logic circuits (logic gates) work. Optionally learn or use a simple multiplication algorithm. You might want to start with the long-...


4

Yes, there is an infinite class of 2-connected cubic graphs on which Hamilton Cycle has a polynomial-time algorithm. Further, there is a such a class that contains infinitely many Hamiltonian graphs and infinitely many non-Hamiltonian graphs, which I think is a decent definition of "non-trivial". First, let $H_n$ be the union of a $2n$-cycle on vertices $\{...


4

Remember that given the HAMPATH instance, you are constructing the DPATH instance. As long as it's a valid instance of DPATH, it's a Yes-instance if and only if the HAMPATH instance is, and it's computable in polynomial time, you can do whatever you want. So in particular, you get to pick how long the sequence is, you can pick any $a_{i}$ to be $s$ or $t$ (...


4

I'm not sure what you mean by an efficient algorithm, but the problem of finding any Hamiltonian path is NP-complete, which means that it is very unlikely that a polynomial time algorithm exists for your problem. If the number of people $n$ is small, say less than 10, then it is feasible to solve the problem by brute force. Generate all $n!$ permutations of ...


4

Proof by induction Basis. All complete oriented digraphs with two vertices have Hamiltonian path - it's obvious. Induction step. Let's assume that complete oriented digraph $G_{n-1}$ with $(n - 1)$ vertices contains Hamiltonian path $(s, ..., t)$ from vertex $s$ to vertex $t$. We'll show how to build Hamiltonian path for complete oriented digraph $G_n$, ...


4

Grid graphs are finite node-induced graphs of the infinite planar grid (whose vertices are integral points, and two vertices are linked when their Euclidean distance is 1). A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter proved that the Hamiltonian path problem on grid graphs is NP-complete. To reduce that to your problem, suppose the grid graph has $m$ ...


3

You can do slightly better on space by using reservoir sampling. The overall approach we take is the same as suggested by @jnalanko, and it only works well for small enough $n$. We generate each permutation of $\{1,\ldots,n\}$, but only keep one solution $X$ stored. At the end, $X$ will satisfy the property of being sampled uniformly at random from the set ...


3

When a problem is NP-complete, it doesn't necessarily mean that all instances are hard to solve. It just means that enough instances are hard to solve that, if you could solve this problem efficiently, you could do the same for all problems in NP. Enough, in this case, does mean infinitely many1 and that should lead you towards looking at large inputs if you ...


3

It is enough to prove your claim for the case of a tournament, in which for every pair of vertices $v\neq w$, exactly one of the edges $(v,w),(w,v)$ is in the graph. Wikipedia has an algorithmic proof that every such graph has a Hamiltonian path. If the tournament is strongly connected, it has a Hamiltonian cycle.


3

there are several ways to conceptualize this, esp using the psychological concept of chunking which is rougly equivalent to the use of "abstraction(s)" in CS. what part is hard to understand? the conversion of factoring to SAT is much easier to understand if you learn how EE circuits implement binary arithmetic (mainly addition), and to note that ...


3

Just add the constraint that $x_{1j}=x_{nj}$ for all $j$, and make a special exception to constraint 2 so that you omit constraint 2 in the case where $i=1$ and $k=n$. Everything works fine for a directed graph. You just need to interpret constraint 5 appropriately.


3

There isn't going to be a fast algorithm for this problem. The class of graphs you're dealing with is, in some of the literature, called grid graphs. That is, they're finite induced subgraphs of the infinite graph with vertices $\mathbb{Z}\times\mathbb{Z}$ with an edge from $(x,y)$ to $(x',y')$ if, and only if, $|x-x'|+|y-y'|=1$. Itai, Papadimitriou and ...


3

Any problem in NP that contains an NP-complete problem as a special case is NP-complete. Any algorithm that can solve the $k$-Hamiltonian path problem must, in particular, be able to solve the case $k=1$, which is just an ordinary Hamiltonian path. We can obviously verify a claimed $k$-Hamiltonian path in polynomial time, so the problem remains in NP. ...


2

Reduction $HC \leq SubgraphIsomorphism$ is done as $G \rightarrow \langle G, C_n \rangle$ where $n$ is the number of vertices in $G$, and $C_n$ is the cycle graph with $n$ vertices. This effectively means that $G$ has a subgraph $C_n$ if and only if $G$ has a Hamiltonian Circuit. There are mainly three types of common reductions. $A \leq_L B$, $A \leq_P B$ ...


2

Other way than Bondy-Chvátal theorem is brute force search. However brute force search isn't an efficient way of solving this problem - there can be an exponential number of possibilities to test. You won't have to test so many possibilities, if you will try following algorithm: http://arxiv.org/pdf/1405.6347.pdf The main principle of algorithm is "to ...


2

Since you said a $O(n^2)$ time algorithm would still be useful, there is a straightforward dynamic programming algorithm that runs in time $O(n^2)$. In particular, a subproblem is specified by a pair of points $(A',P')$; the problem is to find the best pair of paths from $A' \to B$ and $P' \to Q$, using only points that are to the right of both $A'$ and $P'$...


2

Graphviz should do what you want. http://www.graphviz.org/ You can you use it as program or as a library. If you use as a program, then you just need to write a file of your graphs in the dot language and run graphviz on it. Now, for the hamiltonian problem, you should know that this problem is NP-complete. Brute force is the most obvious solution. But ...


2

The nearest neighbor method is often used as a heuristic for different problems. Sometimes the method gives an effective approximation algorithm as well. You could employ it here as well. Here's a skeleton for a heuristic method that maintains a stack $S$ of vertices representing the resulting simple path. Let $F$ be a set containing forbidden vertices, that ...


2

I have seen both Hamilton path (or Hamilton cycle) and Hamiltonian path (or Hamiltonian cycle). A graph, however, is always Hamiltonian (if it contains a Hamilton/Hamiltonian cycle). Consider for example the titles of two papers: Hamiltonian cycles in random regular graphs (Fenner & Frieze) and Generating and counting Hamilton cycles in random regular ...


2

The misunderstanding comes from two variations of the TSP problem: The input graph is complete. The input graph is arbitrary. The standard proof above must assume the first variation of TSP. Thus, there is no k-approximation algorithm for the first variation unless $P=NP$. The same result then follows for the second variation due to the fact that the ...


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