I have found this interesting problem in graph theory and geometry which is allegedly an open problem but latest status seems to be from 01/25/02. I can't seem to find any more information about it, not even other papers describing it.


  • $\begingroup$ If you figure out the vertices that you need to connect, this becomes a MST (P). But figuring out which vertices you need to connect seems pretty much non-trivial. $\endgroup$ May 26, 2020 at 5:49
  • 1
    $\begingroup$ Dozed12, I encourage you to edit the question to summarize the problem in text (not in an image), so it can be found by search, and so it is accessible to individuals with visual impairments. $\endgroup$
    – D.W.
    May 26, 2020 at 6:22
  • $\begingroup$ There is likely no harm in emailing the author of the slides (D. Eppstein) and asking about it. $\endgroup$
    – Juho
    May 26, 2020 at 6:58

1 Answer 1


This problem has been studied since 2002, under the name minimum-length corridor problem.

The problem is known to be NP-complete[1,2], but there is a constant factor polynomial time approximation algorithm[3].

There is more work on this problem, which you can find by searching the citation network of the papers below.

[1]: GONZALEZ-GUTIERREZ, Arturo; GONZALEZ, Teofilo F. Complexity of the minimum-length corridor problem. Computational Geometry, 2007, 37.2: 72-103.

[2]: BODLAENDER, Hans L., et al. On the minimum corridor connection problem and other generalized geometric problems. Computational Geometry, 2009, 42.9: 939-951.

[3]: GONZALEZ-GUTIERREZ, Arturo; GONZALEZ, Teofilo F. Approximation Algorithms for the Minimum-Length Corridor and Related Problems. In: CCCG. 2007. p. 253-256.

  • $\begingroup$ Exactly what I'm looking for, thank you and sorry for late acceptance of answer! $\endgroup$
    – Dozed12
    Jun 9, 2020 at 21:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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