# Tag Info

In the Graph Homomorphism problem, the input is two graphs $G$ and $H$ and the question is whether there is a mapping $h$ from the vertices of $G$ to the vertices of $H$ such that for every edge $uv\... 11 votes ### Problems with Unknown Single Exponential Time Agorithms Update 28 Sep 2020: This has been resolved by Wiebking in SODA '20, where he gave a$2^{O(n)}$-time algorithm, with no remaining dependence on$|G|$. (I'll leave up the rest of the answer for ... 10 votes ### Problems with Unknown Single Exponential Time Agorithms Computing the crossing number of a graph. Existing exact algorithms involve formulating it as an integer linear program with a number of variables cubic in the number of edges [Chimani et al, ESA 2008]... 8 votes ### Applications of Hamiltonian Cycle Problem One application involves stripification of triangle meshes in computer graphics — a Hamiltonian path through the dual graph of the mesh (a graph with a vertex per triangle and an edge when two ... 7 votes ### Applications of Hamiltonian Cycle Problem I think there are some applications in electronic circuit design/construction; for example Yi-Ming Wang, Shi-Hao Chen, Mango C. -T. Chao. An Efficient Hamiltonian-cycle power-switch routing for MTCMOS ... 5 votes ### Applications of Hamiltonian Cycle Problem (Variants of the) TSP show(s) up routinely in several routing and scheduling problems (think of the route planned for a UPS truck out of delivering packages, for instance). But a great place to learn ... 4 votes ### Problems with Unknown Single Exponential Time Agorithms The problem of testing whether a given integer linear program$L$with$n$variables has a feasible solution can be solved using$n^{2.5n+o(n)}\cdot |L|$arithmetic operations. It is a major open ... 4 votes ### Problems with Unknown Single Exponential Time Agorithms Tensor Isomorphism. The best-known algorithm for 3-Tensor Isomorphism over$\mathbb{F}_q$takes time$q^{\Theta(n^2)}$, and over$\mathbb{R}$or$\mathbb{C}$takes times$2^{\Theta(n^2)}$. (The same ... 4 votes Accepted ### On the paper "Quantum Computing Hamiltonian cycles" I emailed the author. He replied "yes that paper is wrong!". He has lost the passwords to remove it from the web. 3 votes Accepted ### Is balanced Hamiltonian cycle NP complete on maximal plane graphs? Yes, it is still$NP$complete. This is because of: Claim: All Hamiltonian cycles on maximal planar graphs are balanced. Proof: This is a special case of Grinberg's theorem: https://en.wikipedia.org/... 3 votes ### What are the known classes of undirected graphs such that every graph belonging to that class is guaranteed to have a Hamiltonian Path? A good resource to answer questions like this is graphclasses.org. You find the graph class you care about -- in this case, Hamiltonian graphs. Then check the maximal subclasses section, and ... 2 votes ### Problems with Unknown Single Exponential Time Agorithms In a recent paper by Fomin et al. (Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds) it is shown that computing the Hadwiger number of a graph has the complexity ... 2 votes ### Best Hamiltonian Cycle Problem solver I found myself having to find a Hamilton path in a graph of 200 vertices (what you called "nodes"). My first idea was to use the Hamilton path solver in Maxima ( http://maxima.sourceforge.net/docs/... 2 votes ### Hamiltonian Cycle as an integer linear programming problem I know this is old, but-- First, make this a 'directed' cycle: only one$e_{ij}$is true on each vertex, so that$v_i = 1$. This will enable a sort of useful indexing on the cycle. Next, create ... 2 votes Accepted ### Complexity of finding a path visiting all leaves on a tree while respecting a distance bound As the comments have suggested, you are looking for a Ham Path through a set nodes in the$k$-leaf power graph of this tree. That is, given your tree$T$and a distance$k$, form a graph$G$where$V(...
If $G$ has a disjoint vertex cycle cover then I agree that $H$ must have a perfect matching, but I don't see the other direction (or I have misunderstood how you define $H$ exactly). I think the ...