Document Open Access Logo

Eulerian Paths with Regular Constraints

Authors Orna Kupferman, Gal Vardi

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.62.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Orna Kupferman
Gal Vardi

Cite AsGet BibTex

Orna Kupferman and Gal Vardi. Eulerian Paths with Regular Constraints. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.62

Abstract

Labeled graphs, in which edges are labeled by letters from some alphabet Sigma, are extensively used to model many types of relations associated with actions, costs, owners, or other properties. Each path in a labeled graph induces a word in Sigma^* -- the one obtained by concatenating the letters along the edges in the path. Classical graph-theory problems give rise to new problems that take these words into account. We introduce and study the constrained Eulerian path problem. The input to the problem is a Sigma-labeled graph G and a specification L \subseteq Sigma^*. The goal is to find an Eulerian path in G that satisfies L. We consider several classes of the problem, defined by the classes of G and L. We focus on the case L is regular and show that while the problem is in general NP-complete, even for very simple graphs and specifications, there are classes that can be solved efficiently. Our results extend work on Eulerian paths with edge-order constraints. We also study the constrained Chinese postman problem, where edges have costs and the goal is to find a cheapest path that contains each edge at least once and satisfies the specification. Finally, we define and study the Eulerian language of a graph, namely the set of words along its Eulerian paths.
Keywords
  • Eulerian paths
  • regular languages

Metrics

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

References

  1. S. Abiteboul and V. Vianu. Regular path queries with constraints. J. Comput. Syst. Sci., 58(3):428-452, 1999. Google Scholar
  2. E. Anshelevich, A. Dasgupta, J. Kleinberg, E. Tardos, T. Wexler, and T. Roughgarden. The price of stability for network design with fair cost allocation. SIAM J. Comput., 38(4):1602-1623, 2008. Google Scholar
  3. G. Avni, O. Kupferman, and T. Tamir. Network-formation games with regular objectives. In Proc. 17th Int. Conf. on Foundations of Software Science and Computation Structures, volume 8412 of Lecture Notes in Computer Science, pages 119-133. Springer, 2014. Google Scholar
  4. C. Barrett, R. Jacob, and M. Marathe. Formal-language-constrained path problems. SIAM Journal on Computing, 30(3):809-837, 2000. Google Scholar
  5. V. Blue, J. Adler, and G. List. Real-time multiple-objective path search for in-vehicle route guidance systems. Journal of the Transportation Research Board, 1588:10-17, 1997. Google Scholar
  6. P.G. Bradford and D.A. Thomas. Labeled shortest paths in digraphs with negative and positive edge weights. RAIRO-Theoretical Informatics and Applications, 43(03):567-583, 2009. Google Scholar
  7. A.L. Buchsbaum, P.C. Kanellakis, and J.S. Vitter. A data structure for arc insertion and regular path finding. Annals of Mathematics and Artificial Intelligence, 3(2-4):187-210, 1991. Google Scholar
  8. D. Calvanese, G. De Giacomo, M. Lenzerini, and M.Y. Vardi. Reasoning on regular path queries. ACM SIGMOD Record, 32(4):83-92, 2003. Google Scholar
  9. W. Cheng and M. Pedram. Power-optimal encoding for a DRAM address bus. IEEE Trans. VLSI Syst., 10(2):109-118, 2002. Google Scholar
  10. T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. MIT Press and McGraw-Hill, 1990. Google Scholar
  11. M. Dror, H. Stern, and P. Trudeau. Postman tour on a graph with precedence relation on arcs. Networks, 17(3):283-294, 1987. Google Scholar
  12. H.A. Eiselt, M. Gendreau, and G. Laporte. Arc routing problems, part i: The chinese postman problem. Operations Research, 43(2):231-242, 1995. Google Scholar
  13. L.R. Ford and D.R. Fulkerson. Flows in networks. Princeton Univ. Press, Princeton, 1962. Google Scholar
  14. S. J. Fortune, J. Hopcroft, and J. Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10:11-121, 1980. Google Scholar
  15. M. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. Freeman and Co., 1979. Google Scholar
  16. G. Ghiani and G. Improta. An algorithm for the hierarchical chinese postman problem. Operations Research Letters, 26(1):27-32, 2000. Google Scholar
  17. S. Hannenhalli, W. Feldman, H.F. Lewis, S.S. Skiena, and P.A. Pevzner. Positional sequencing by hybridization. Computer applications in the biosciences: CABIOS, 12(1):19-24, 1996. Google Scholar
  18. T. Ibaraki and S. Poljak. Weak three-linking in eulerian digraphs. SIAM journal on Discrete Mathematics, 4(1):84-98, 1991. Google Scholar
  19. J. Kari. Synchronizing finite automata on Eulerian digraphs. Theoretical Computer Science, 295:223-232, 2003. Google Scholar
  20. K.I. Kawarabayashi, Y. Kobayashi, and B. Reed. The disjoint paths problem in quadratic time. Journal of Combinatorial Theory, Series B, 102(2):424-435, 2012. Google Scholar
  21. H.L.M. Kerivin, M. Lacroix, and A.R. Mahjoub. On the complexity of the Eulerian closed walk with precedence path constraints problem. Theoretical Computer Science, 439:16-29, 2012. Google Scholar
  22. P. Korteweg and T. Volgenant. On the hierarchical chinese postman problem with linear ordered classes. European Journal of Operational Research, 169(1):41-52, 2006. Google Scholar
  23. O. Kupferman and T. Tamir. Properties and utilization of capacitated automata. In Proc. 34th Conf. on Foundations of Software Technology and Theoretical Computer Science, volume 29 of LIPIcs, pages 33-44. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2014. Google Scholar
  24. A.O. Mendelzon and P.T. Wood. Finding regular simple paths in graph databases. SIAM Journal on Computing, 24(6):1235-1258, 1995. Google Scholar
  25. E. Moreno and M. Matamala. Minimal Eulerian circuit in a labeled digraph. In LATIN 2006: Theoretical Informatics, pages 737-744. Springer, 2006. Google Scholar
  26. G. Naves and A. Sebő. Multiflow feasibility: an annotated tableau. In Research Trends in Combinatorial Optimization, pages 261-283. Springer, 2009. Google Scholar
  27. P.A. Pevzner, H. Tang, and M.S. Waterman. An Eulerian path approach to dna fragment assembly. Proceedings of the National Academy of Sciences, 98(17):9748-9753, 2001. Google Scholar
  28. N. Robertson and P.D. Seymour. Graph minors. xiii. the disjoint paths problem. Journal of combinatorial theory, Series B, 63(1):65-110, 1995. Google Scholar
  29. J. Vygen. Disjoint paths. report no. 94816. Research Institute for Discrete Mathematics, University of Bonn, 1994. Google Scholar
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 Imprint Privacy Contact