Tag Info

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

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

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

5

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

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

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

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

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

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

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 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$... 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 ... 4 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.$$ 4 The complete digraph of$n$nodes,$K_n$has$n(n-1)$edges. Describe a digraph of$n$nodes with$n(n-1)-\delta$edges as a digraph "with$\delta$edges removed". A proof by induction The following is an outline to prove by induction that every digraph of$n$nodes with$n-2$edges removed contains a Hamiltonian cycle. The base case, when$n=2$or ... 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 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 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 ... 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 How about: Start with a fully connected graph. Choose a random permutation of the list of all nodes - this will be our guaranteed Hamiltonian cycle. Delete an edge from the graph at random, as long as it is not in our protected HC path going to leave any vertex with too few edges. Repeat step 3 until all your vertices have a degree in your required range. ... 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. ... 3 Hamiltonian Path in a DAG is easy to solve: You can find the longest path in$O(|V|+|E|)$time using the critical path algorithm: https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths. For unweighted DAGs, this sounds like essentially the same thing as your topological sort. Hamiltonian Path is NP-hard on digraphs with cycles,... 3 Usually, when we talk about the complexity of an optimisation problem (a problem where want to maximise of mininise some value, here the length of a Hamiltonian cycle), we actually look at the complexity of the decision version of that problem. Here, the decision version is: Does the weighted graph$G\$ have a Hamiltonian path with total weight at least ...

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

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