skip to content

A cleaning route must cover every corridor once; the revised route must visit every room once — why does the second become NP-complete?

level: seniorimportance: should knowfreq 38%

answer

  1. edges once versus vertices once
  2. what one pass through a vertex uses
  3. a local, additive counting test
  4. one component plus even degrees
  5. no degree rule settles the vertex version

basics

~20 s

Covering every edge once has a local test: each pass through a vertex uses two edge-ends, so every vertex needs even degree, and one component plus even degrees is enough. Visiting every vertex once has no such local characterisation, and deciding it is NP-complete.

solid answer

~50 s

An Euler circuit uses every edge exactly once. Each time the walk passes through a vertex it consumes one edge-end arriving and one leaving, so every vertex must have even degree; provided all edges lie in one connected component that condition is also sufficient, and the circuit can be assembled by splicing closed walks together in time linear in the edges. The test is local and additive — look at each vertex on its own and count. A Hamiltonian cycle uses every *vertex* exactly once, and no degree condition characterises it: you can build graphs where every vertex has large even degree and no such cycle exists, and sparse graphs where one does. Committing to two edges at a vertex rules out options arbitrarily far away, which is why the decision is NP-complete rather than a counting check.

code

pseudocode · 11 lines
pseudocode
odd = 0
for each vertex v with degree(v) > 0:
    if degree(v) is odd:
        odd = odd + 1

if the edges do not all lie in one connected component:
    return NO_EDGE_TOUR        // isolated vertices are ignored above

if odd == 0: return CLOSED_EDGE_TOUR
if odd == 2: return OPEN_EDGE_TOUR_ONLY
return NO_EDGE_TOUR

go deeper

for a junior

Keep the pair straight: every edge once has a degree test you can carry out by counting, every vertex once does not. Naming which is which is the recall this question wants.

for a middle

Explain why parity is the right invariant — each pass through a vertex uses two edge-ends — and say that even degrees plus one component is sufficient, not merely necessary.

for a senior

When a requirement shifts from covering links to covering sites, say out loud that the classification changed and what you will do instead of promising an exact algorithm. Catching the switch early is the whole point.

for a principal

Own the conversation about wording. A rule that every site is entered exactly once is far more expensive to honour than one that merely bounds revisits, and which wording ships decides what the team can promise.

## Two tours that sound alike Model the building as a graph: rooms are vertices, corridors are edges. - An **Euler circuit** is a closed walk using every *edge* exactly once. Vertices may be revisited freely. - A **Hamiltonian cycle** is a closed walk visiting every *vertex* exactly once. Edges are mostly unused. Swapping "corridor" for "room" in a requirement changes one word and moves the problem across the feasibility line. Deciding whether an Euler circuit exists is a counting exercise; deciding whether a Hamiltonian cycle exists is NP-complete. ## Why parity settles the edge tour The argument for **necessity** is one sentence. Every time the walk passes through a vertex it uses one edge-end to arrive and one to leave, so the edges at that vertex are consumed in pairs. A closed walk that uses *all* of them therefore needs each vertex to have an even number of edge-ends — an even degree. A vertex of odd degree would strand one edge. The less obvious half is that the condition is also **sufficient**, provided all the edges lie in one connected component (isolated vertices with no edges are harmless and can be ignored): 1. Start anywhere and walk along unused edges. Even degrees guarantee that whenever you enter a vertex that is not the start, an unused edge is available to leave by — so the walk can only get stuck back where it began, closing a loop. 2. If unused edges remain, pick a vertex on the loop that still has one and build a second closed walk the same way. 3. Splice the second loop into the first at that vertex, and repeat until no edges remain. The whole construction touches each edge a constant number of times, so it runs in time linear in the number of edges. The related open version follows from the same counting: a walk covering every edge once but starting and ending at different rooms exists exactly when there are precisely two odd-degree vertices, and those two are the endpoints. The key property is that the test is **local and additive**. Each vertex is examined alone, the results are combined by counting, and nothing about one vertex changes the verdict at another. ## Why nothing similar settles the vertex tour For a Hamiltonian cycle there is no local invariant to count. Choosing the two edges used at one vertex forbids its other edges, which changes what is available at its neighbours, which changes their neighbours, and the consequences spread without limit. Some observations that sharpen the point: - **Degrees do not decide it.** Graphs exist where every vertex has a large even degree and no Hamiltonian cycle exists, and very sparse graphs that have one. - **Sufficient conditions exist, but none is also necessary.** For instance, a graph in which every vertex is adjacent to at least half of the others always has a Hamiltonian cycle. That helps on the graphs that satisfy it and says nothing about the rest — which is precisely the undecided set. - **Restriction does not rescue it.** The decision stays NP-complete on planar graphs in which every vertex has exactly three neighbours, so "my graph is a floor plan and sparse" is not an escape. | Requirement | Object covered | Cost of deciding | What decides it | |---|---|---|---| | Every corridor exactly once, closed | Edges | Linear in edges | One component plus all degrees even | | Every corridor exactly once, open ends | Edges | Linear in edges | One component plus exactly two odd degrees | | Every room exactly once, closed | Vertices | NP-complete | No local characterisation known | ## Reading it back into the requirement The engineering value is in hearing the switch. When a specification moves from "cover every link" to "visit every site", the right response is to say that the classification just changed, before anyone has committed to an exact algorithm in a scheduler. Two follow-ups usually matter more than the theory: 1. **Is "exactly once" load-bearing?** Requirements often mean "do not waste time revisiting", not "revisiting is forbidden". Bounding revisits is a materially different demand from forbidding them. 2. **Which object is really being covered?** People say "visit every room" when what they are charged for is corridors walked. Getting the object right can put the requirement back on the easy side by itself. That pair — hearing the switch, then interrogating the wording — is what distinguishes an answer grounded in production from a recital of two theorems.

  • If the edges form one component and all degrees are even, how is the circuit actually built?
    By splicing closed walks. Follow unused edges from any vertex until you return to the start — even degrees mean you can never get stuck anywhere else. If edges remain, start a second closed walk at a vertex of the first that still has unused edges, and insert it into the tour at that point. Repeating costs time linear in the edges.
  • Do sufficient conditions for a Hamiltonian cycle exist, and why do they not make the problem easy?
    They do — for example, a graph where every vertex is adjacent to at least half the others always has one. But they are sufficient and never necessary, so the graphs that fail them are exactly the ones still in question. The general decision is untouched and remains NP-complete.

saying these in an interview costs you the question

  • Treats a route over every edge and a route over every vertex as one problem.
  • Claims even degrees at every vertex imply a Hamiltonian cycle as well.
  • Requires the whole graph to be connected, forgetting isolated vertices are harmless.
  • Says the vertex tour is hard purely because its search space is bigger.
  • Mixes the circuit and path conditions, allowing odd-degree vertices in a closed tour.