E. Koutsoupias, C. Papadimitriou, and M. Yannakakis.

**Searching a fixed graph.**In*International Colloquium on Automata, Languages, and Programming*, pages 280--289, Paderborn, Germany, 8--12 July 1996.### Abstract

We study three combinatorial optimization problems related to searching a graph that is known in advance, for an item that resides at an unknown node. The*search ratio*of a graph is the optimum

*competitive ratio*(the worst-case ratio of the distance traveled before the unknown node is visited, over the distance between the node and a fixed root, minimized over all Hamiltonian walks of the graph). We also define the

*randomized search ratio*(we minimize over all

*distributions*of permutations). Finally, the

*traveling repairman problem*seeks to minimize the expected time of visit to the unknown node, given some distribution on the nodes. All three of these novel graph-theoretic parameters are NP-complete ---and MAXSNP-hard--- to compute exactly; we present interesting approximation algorithms for each. We also show that the randomized search ratio and the traveling repairman problem are related via

*duality*and

*polyhedral separation*.

### Bib

@string{ICALP96 = {International Colloquium on Automata, Languages, and Programming}} @InProceedings{KPY96, author = {E. Koutsoupias and C. Papadimitriou and M. Yannakakis}, title = {Searching a fixed graph}, booktitle = ICALP96, pages = {280--289}, address = {Paderborn, Germany}, month = {8--12 } # jul, year = 1996 }