CS 163/265, Winter 2025, Practice Problem Set 5

Find an undirected graph with positive edge weights that has a Hamiltonian cycle, but for which the shortest Hamiltonian cycle is not the optimal traveling salesperson tour (using the definition of the optimal tour from the lecture notes). Hint: your edge weights will need to disobey the triangle inequality.
A "triangle graph" with three vertices and three edges has edge weights $x$ , $y$ , and $z$ . For which values of $x$ , $y$ , and $z$ will the MST-doubling heuristic (without taking shortcuts, so producing a tour with four steps through two doubled edges) produce the optimal traveling salesperson tour?
Suppose your computer is fast enough that, in less than one minute, it can complete either the $O ((n - 1)!)$ -time brute force search for the traveling salesperson problem for inputs of size $n = 17$ , or the $O (n^{2} 2^{n})$ -time dynamic programming algorithm for the same problem for inputs of size $n = 34$ . Based only on their worst case time analysis, what size of problem should your computer be able to solve using the same algorithms in less than one hour?
A graph, given to you as input, has been generated by the Barabasi-Albert model with parameter $d$ , starting from a complete graph $K_{d}$ . However, you have not been told what the value of $d$ is. Describe how to determine $d$ from the numbers of vertices and edges ( $n$ and $m$ ) in your graph. (You may assume that each new vertex chooses its neighbors randomly without replacement, so that it gets exactly $d$ distinct neighbors.)