The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Tag Info

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

2

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

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

1

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

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.

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

Basically, Hamiltonian Cycle is the parcel problem with just one driver. To reduce Hamiltonian Cycle to the parcel problem with two drivers, you get one of the drivers to solve your Hamiltonian Cycle problem, and you make enough work for the other driver that they can't "cheat" by helping the first driver (but not so much work that the first driver has to ...

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