Document Open Access Logo

K-Best Solutions of MSO Problems on Tree-Decomposable Graphs

Authors David Eppstein, Denis Kurz

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2017.16.pdf
  • Filesize: 498 kB
  • 13 pages

Document Identifiers

Author Details

David Eppstein
Denis Kurz

Cite As Get BibTex

David Eppstein and Denis Kurz. K-Best Solutions of MSO Problems on Tree-Decomposable Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.IPEC.2017.16

Abstract

We show that, for any graph optimization problem in which the feasible solutions can be expressed by a formula in monadic second-order logic describing sets of vertices or edges and in which the goal is to minimize the sum of the weights in the selected sets, we can find the k best solution values for n-vertex graphs of bounded treewidth in time O(n + k log n). In particular, this applies to finding the k shortest simple paths between given vertices in directed graphs of bounded treewidth, giving an exponential speedup in the per-path cost over previous algorithms.

Subject Classification

Keywords
  • graph algorithm
  • k-best
  • monadic second-order logic
  • treewidth

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Selim G. Akl. Design and analysis of parallel algorithms. Prentice Hall, 1989. Google Scholar
  2. Stefan Arnborg, Bruno Courcelle, Andrzej Proskurowski, and Detlef Seese. An algebraic theory of graph reduction. J. ACM, 40(5):1134-1164, 1993. URL: http://dx.doi.org/10.1145/174147.169807.
  3. Stefan Arnborg, Jens Lagergren, and Detlef Seese. Easy problems for tree-decomposable graphs. J. Algorithms, 12(2):308-340, 1991. URL: http://dx.doi.org/10.1016/0196-6774(91)90006-K.
  4. Michel Bauderon and Bruno Courcelle. Graph expressions and graph rewritings. Mathematical Systems Theory, 20(2-3):83-127, 1987. URL: http://dx.doi.org/10.1007/BF01692060.
  5. Hans L. Bodlaender. Nc-algorithms for graphs with small treewidth. In Jan van Leeuwen, editor, Graph-Theoretic Concepts in Computer Science, 14th International Workshop, WG '88, Amsterdam, The Netherlands, June 15-17, 1988, Proceedings, volume 344 of Lecture Notes in Computer Science, pages 1-10. Springer, 1988. URL: http://dx.doi.org/10.1007/3-540-50728-0_32.
  6. Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305-1317, 1996. URL: http://dx.doi.org/10.1137/S0097539793251219.
  7. Hans L. Bodlaender and Torben Hagerup. Parallel algorithms with optimal speedup for bounded treewidth. SIAM J. Comput., 27(6):1725-1746, 1998. URL: http://dx.doi.org/10.1137/S0097539795289859.
  8. Chandra R. Chegireddy and Horst W. Hamacher. Algorithms for finding k-best perfect matchings. Discrete Applied Mathematics, 18(2):155-165, 1987. URL: http://dx.doi.org/10.1016/0166-218X(87)90017-5.
  9. Bruno Courcelle. Graph rewriting: An algebraic and logic approach. In Handbook of Theoretical Computer Science, Vol. B: Formal Models and Semantics, pages 193-242. Elsevier, 1990. Google Scholar
  10. Bruno Courcelle and Mohamed Mosbah. Monadic second-order evaluations on tree-decomposable graphs. Theor. Comput. Sci., 109(1&2):49-82, 1993. URL: http://dx.doi.org/10.1016/0304-3975(93)90064-Z.
  11. Edo S. Van der Poort, Marek Libura, Gerard Sierksma, and Jack A. A. van der Veen. Solving the k-best traveling salesman problem. Computers & OR, 26(4):409-425, 1999. URL: http://dx.doi.org/10.1016/S0305-0548(98)00070-7.
  12. James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, and Robert Endre Tarjan. Making data structures persistent. J. Comput. Syst. Sci., 38(1):86-124, 1989. URL: http://dx.doi.org/10.1016/0022-0000(89)90034-2.
  13. Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace versions of the theorems of bodlaender and courcelle. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 143-152. IEEE Computer Society, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.21.
  14. David Eppstein. Finding the k shortest paths. SIAM J. Comput., 28(2):652-673, 1998. URL: http://dx.doi.org/10.1137/S0097539795290477.
  15. David Eppstein. K-best enumeration. Bull. EATCS, 115, 2015. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/322.
  16. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification - a technique for speeding up dynamic graph algorithms. J. ACM, 44(5):669-696, 1997. URL: http://dx.doi.org/10.1145/265910.265914.
  17. S. Feferman and R. L. Vaught. The first order properties of products of algebraic systems. Fund. Math., 47:57-103, 1959. Google Scholar
  18. Greg N. Frederickson. An optimal algorithm for selection in a min-heap. Inf. Comput., 104(2):197-214, 1993. URL: http://dx.doi.org/10.1006/inco.1993.1030.
  19. Harold N. Gabow. Two algorithms for generating weighted spanning trees in order. SIAM J. Comput., 6(1):139-150, 1977. URL: http://dx.doi.org/10.1137/0206011.
  20. H. W. Hamacher and M. Queyranne. K best solutions to combinatorial optimization problems. Ann. Oper. Res., 4(1-4):123-143, 1985. URL: http://dx.doi.org/10.1007/BF02022039.
  21. Naoki Katoh, Toshihide Ibaraki, and Hisashi Mine. An efficient algorithm for K shortest simple paths. Networks, 12(4):411-427, 1982. URL: http://dx.doi.org/10.1002/net.3230120406.
  22. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 645-654. IEEE Computer Society, 2010. URL: http://dx.doi.org/10.1109/FOCS.2010.67.
  23. Jin Y. Yen. Finding the K shortest loopless paths in a network. Manag. Sci., 17(11):712-716, 1971. URL: http://www.jstor.org/stable/2629312.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact