Tours over sites whose costs obey the triangle inequality admit a 3/2 guarantee, while arbitrary edge costs admit no constant factor unless P = NP — what makes the difference?
answer
- the property is about three sites
- shortcutting is what it licenses
- spanning structure, walk, skip repeats
- price missing links enormously
- a gap an approximation would resolve
basics
~20 sThe triangle inequality lets an algorithm skip an already-visited site without paying more, so a cheap structure spanning all sites can be converted into a tour of comparable cost. With arbitrary costs, missing connections can be priced so high that any constant-factor approximation would decide Hamiltonicity.
solid answer
~50 sEvery constant-factor argument for tours leans on **shortcutting**: build something cheap that touches every site, walk it, and skip repeats. That skip is only safe when going directly from one site to another costs no more than going via a third — the triangle inequality. Under it, a spanning structure gives a factor of 2, and a more careful construction gives 3/2. Drop the inequality and the picture collapses: take any graph, price its edges at 1 and every missing connection at some enormous `M`. If a Hamiltonian cycle exists the optimal tour costs `n`; if not, every tour must use a missing connection and costs at least `n - 1 + M`. Choosing `M` above `rho * n` means a `rho`-approximation's output alone tells the two cases apart, so it would decide an NP-complete problem. Since `M` is written in binary, this rules out constant and even rapidly growing factors unless P = NP.
go deeper
Remember that the well-known tour guarantee assumes costs where going direct is never worse than going via a detour, and that without that assumption no factor can be promised.
Explain shortcutting: a walk over a cheap spanning structure revisits sites, and the triangle inequality is what makes skipping those revisits free, which is how the walk becomes a tour without losing the bound.
Demonstrate the gap construction. Price present edges at one and missing ones enormously, show the two optima separate, and conclude that any ratio would decide an NP-complete problem in polynomial time.
The lever is modelling. Whether your cost matrix satisfies the inequality decides whether a bounded promise is available at all, so treat that as a design decision made early rather than a property discovered late.
## The property the guarantee actually rests on The **triangle inequality** says that for any three sites, the direct cost from the first to the third is at most the cost of going via the second. Costs derived from distances, latencies measured over a network that routes freely, or any metric satisfy it; arbitrary business costs, one-way pricing and forbidden links generally do not. Why does an approximation care? Because every cheap-tour argument in this family has the same three-step shape: 1. build a structure that touches every site and whose cost is provably at most the optimal tour's cost; 2. walk that structure, which visits some sites more than once; 3. **shortcut** — delete repeat visits by jumping straight to the next unvisited site. Step three is where the property pays. Each shortcut replaces a path through visited sites with a direct hop, and the triangle inequality says the hop costs no more. So the walk's cost survives the conversion into a genuine tour, and whatever bound step one established is preserved. A spanning structure doubled and shortcut yields a factor of **2**; refining step one so that the walk is built from the spanning structure plus a cheapest pairing of its odd-degree sites yields **3/2**, the figure usually quoted. A much later result shaves an almost imperceptible amount below 3/2, which changes the theory and nothing else. ## Removing the property removes everything With arbitrary costs there is no constant-factor approximation at all unless P = NP, and the argument is a **gap reduction** — the standard way inapproximability is proved. Start from the question "does this graph on `n` vertices contain a cycle visiting every vertex exactly once?", which is NP-complete. Build a tour instance on the same `n` sites: - every edge present in the graph costs **1**; - every missing connection costs **M**, a large number of your choosing. Now the two cases separate cleanly: | Case | Cheapest tour costs | Why | |---|---|---| | The graph has a Hamiltonian cycle | exactly `n` | the cycle uses `n` real edges at cost 1 each | | It does not | at least `n - 1 + M` | any tour must traverse at least one missing connection | Suppose a polynomial-time `rho`-approximation existed. Set `M = rho * n`. On a yes-instance it must return at most `rho * n`; on a no-instance even the optimum is at least `n - 1 + rho * n`, which exceeds `rho * n` for any `n >= 2`. So reading the returned cost decides Hamiltonicity in polynomial time, forcing P = NP. Two details make the result stronger than it first looks: - `M` is written in binary, so it costs only a polynomial number of bits even when astronomically large. The same argument therefore rules out not just constant factors but any factor computable from the input size. - Nothing about the algorithm was assumed except its ratio. Inapproximability results constrain **all** polynomial-time algorithms, not merely the natural ones. ## What the contrast teaches The practical lesson is that the *modelling choice* determines which guarantees are available to you. - If your costs genuinely form a metric, constant-factor machinery is on the table and you can promise a bounded ratio. - If your costs include forbidden or punitive links, you are in the general case, and no ratio at all is provable — you can still run something and measure it, but you cannot write a factor into a commitment. - Sometimes a modelling change restores the property: replacing a direct cost with the cheapest indirect route between the same two sites produces costs that do satisfy the inequality, and the resulting tour can be expanded back. Whether that substitution is faithful to the real problem is a judgment call, not a theorem. ## The framing an interviewer is listening for Weak answers treat 3/2 as a fact about tours and stop. The point being probed is **conditional**: the ratio is a property of the cost structure, not of the problem name. A strong answer names the triangle inequality, says explicitly that shortcutting is what it licenses, and then explains that in its absence the gap construction turns any ratio into a decision procedure for an NP-complete problem. That last move — hardness of *approximation* proved by manufacturing a gap that an approximation would have to resolve — is the transferable idea, and it recurs wherever a threshold below which approximation becomes NP-hard is quoted.
- Why does writing the huge cost `M` in binary make the inapproximability result stronger?Because `M` costs only about `log M` bits, so even an astronomically large value keeps the constructed instance polynomial in size. That lets you set `M` against any factor computable from the input size, not merely a constant, and the same argument rules all of them out unless P = NP.
- Can a general-cost instance be converted into one that satisfies the triangle inequality?You can replace each pairwise cost with the cheapest indirect route between those two sites, which does satisfy the inequality, and a tour there expands back into a walk over the original. That is a genuine technique, but it changes the problem: the expanded walk may revisit sites, so it answers the version that permits revisits, not the one that forbids them.
- If a 2-approximation for metric tours is so much simpler than the 3/2 one, when is the harder construction worth it?Only when the factor itself is the deliverable — a written commitment, or a bound feeding another argument. Both run in polynomial time, and on real inputs each usually lands far under its own bound, so the choice is about what you must promise rather than what you expect to observe.
saying these in an interview costs you the question
- Quotes 3/2 for tours without stating the cost condition it requires.
- Thinks the general case is merely harder rather than provably unapproximable.
- Believes shortcutting is always safe regardless of the cost structure.
- Assumes inapproximability applies only to known algorithms, not all of them.
- Confuses the absence of a ratio with the absence of any usable method.