There are some results/concepts in TCS which are used in areas other than the "home area" where they emerged. For example, NP-completeness has complexity theory as its home area, but it is also used in many papers that are not about complexity theory. This is an indication of the general usefulness and importance of the concept.

Similarly, network flow algorithms, shortest path algorithms etc., have combinatorial optimization as their home area, but are also used in many papers that are not specifically about combinatorial optimization. Graphs have graph theory as their home area, but are used in many other fields, as well.

Question: What are some other, not so obvious or not so well known examples of methods/concepts that also proved useful outside of their home areas?


One thing that immediately comes to mind is that graph k-coloring is used in compilers for register allocation. An instance of register allocation for k registers is solved by reducing into an instance of k-coloring. See, for example, section 8.8 of Aho, Lam, Sethi and Ullman (i.e. Dragon Book).

| cite | improve this answer | |
  • $\begingroup$ I think this is true for many NP-complete (NP-hard by extension) problems. Travelling Salesman, Vehicle Routing, Scheduling,... and many of its variations arise from real-life problems. These real-life problems are often discussed (as they should) in the papers that introduce/discuss the problem/variation. e.g. set.kuleuven.be/codes/itsp_page and related paper arxiv.org/abs/1701.08517 $\endgroup$ – Auberon Apr 14 '18 at 9:35
  • $\begingroup$ @Auberon Indeed. I listed register allocation just because it's a rather unusual (and non-intuitive) instance of graph coloring! $\endgroup$ – xrq Apr 15 '18 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.