Document Open Access Logo

Directed Graph Minors and Serial-Parallel Width

Authors Argyrios Deligkas, Reshef Meir

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.44.pdf
  • Filesize: 0.52 MB
  • 14 pages

Document Identifiers

Author Details

Argyrios Deligkas
  • Leverhulme Research Centre, University of Liverpool, UK
Reshef Meir
  • Faculty of Industrial Engineering and Management, Technion, Israel

Cite As Get BibTex

Argyrios Deligkas and Reshef Meir. Directed Graph Minors and Serial-Parallel Width. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.44

Abstract

Graph minors are a primary tool in understanding the structure of undirected graphs, with many conceptual and algorithmic implications. We propose new variants of directed graph minors and directed graph embeddings, by modifying familiar definitions. For the class of 2-terminal directed acyclic graphs (TDAGs) our two definitions coincide, and the class is closed under both operations. The usefulness of our directed minor operations is demonstrated by characterizing all TDAGs with serial-parallel width at most k; a class of networks known to guarantee bounded negative externality in nonatomic routing games. Our characterization implies that a TDAG has serial-parallel width of 1 if and only if it is a directed series-parallel graph. We also study the computational complexity of finding a directed minor and computing the serial-parallel width.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Mathematics of computing → Graph theory
Keywords
  • directed minors
  • pathwidth

Metrics

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

Related Versions

References

  1. I. Ashlagi, D. Monderer, and M. Tennenholtz. Two-terminal routing games with unknown active players. Artificial Intelligence, 173(15):1441-1455, 2009. Google Scholar
  2. M. Babaioff, R. Kleinberg, and C. Papadimitriou. Congestion games with malicious players. In EC, pages 103-112. ACM, 2007. Google Scholar
  3. A. Blum and M. Furst. Fast planning through planning graph analysis. Artificial intelligence, 90(1-2):281-300, 1997. Google Scholar
  4. C. Chang and J. Slagle. An admissible and optimal algorithm for searching AND/OR graphs. Artificial Intelligence, 2(2):117-128, 1971. Google Scholar
  5. B. Codenotti and M. Leoncini. Parallel Complexity of Linear System Solution. World Scientific, 1991. Google Scholar
  6. D. Cohen, M. Cooper, P. Jeavons, and S. Zivny. Tractable classes of binary csps defined by excluded topological minors. In IJCAI, pages 1945-1951, 2015. Google Scholar
  7. G. Cooper. The computational complexity of probabilistic inference using bayesian belief networks. Artificial intelligence, 42(2-3):393-405, 1990. Google Scholar
  8. E. Demaine, M. Hajiaghayi, and K. Kawarabayashi. Algorithmic graph minor theory: Decomposition, approximation, and coloring. In FOCS, pages 637-646. IEEE, 2005. Google Scholar
  9. R.J Duffin. Topology of series-parallel networks. Journal of Mathematical Analysis and Applications, 10(2):303-318, 1965. Google Scholar
  10. D. Eppstein. Parallel recognition of series-parallel graphs. Inf. and Comp., 98(1):41-55, 1992. Google Scholar
  11. A. Epstein, M. Feldman, and Y. Mansour. Efficient graph topologies in network routing games. Games and Economic Behavior, 66(1):115-125, 2009. Google Scholar
  12. Fortune, Hopcroft, and Wyllie. The directed subgraph homeomorphism problem. TCS: Theoretical Computer Science, 10, 1980. Google Scholar
  13. V. Gogate and R. Dechter. A complete anytime algorithm for treewidth. In UAI, pages 201-208, 2004. Google Scholar
  14. R. Holzman and N. Law-Yone. Network structure and strong equilibrium in route selection games. Mathematical Social Sciences, 46(2):193-205, 2003. Google Scholar
  15. E. Horvitz, J. Breese, and M. Henrion. Decision theory in expert systems and artificial intelligence. International journal of approximate reasoning, 2(3):247-302, 1988. Google Scholar
  16. A. Jakoby, M. Liśkiewicz, and R. Reischuk. Space efficient algorithms for directed series-parallel graphs. Journal of Algorithms, 60(2):85-114, 2006. Google Scholar
  17. T. Johnson, N. Robertson, P. Seymour, and R. Thomas. Directed tree-width. Journal of Combinatorial Theory, Series B, 82(1):138-154, 2001. Google Scholar
  18. T. Johnson, N. Robertson, P. Seymour, and R. Thomas. Excluding a grid minor in planar digraphs. arXiv:1510.00473, 2015. Google Scholar
  19. K. Kawarabayashi and S. Kreutzer. Towards the graph minor theorems for directed graphs. In ICALP, pages 3-10. Springer, 2015. Google Scholar
  20. S. Kintali and Q. Zhang. Forbidden directed minors and kelly-width. arXiv:1308.5170, 2013. Google Scholar
  21. J. Kleinberg and S. Oren. Time-inconsistent planning: a computational problem in behavioral economics. In EC, pages 547-564. ACM, 2014. Google Scholar
  22. S. Kreutzer. Nowhere crownful classes of directed graphs. In Encyclopedia of Algorithms, pages 1416-1419. Springer, 2016. Google Scholar
  23. Casimir Kuratowski. Sur le probleme des courbes gauches en topologie. Fundamenta mathematicae, 15(1):271-283, 1930. Google Scholar
  24. Michael Lampis, Georgia Kaouri, and Valia Mitsou. On the algorithmic effectiveness of digraph decompositions and complexity measures. Discrete Optimization, 8(1):129-138, 2011. Parameterized Complexity of Discrete Optimization. URL: http://dx.doi.org/10.1016/j.disopt.2010.03.010.
  25. László Lovász. Graph minor theory. Bulletin of the American Mathematical Society, 43(1):75-86, 2006. Google Scholar
  26. A. Mackworth. Consistency in networks of relations. In Readings in AI, pages 69-78. Tioga Publ. Col., 1981. Google Scholar
  27. K. Meer. An extended tree-width notion for directed graphs related to the computation of permanents. Computer Science-Theory and Applications, pages 247-260, 2011. Google Scholar
  28. R. Meir and D. Parkes. Playing the wrong game: Bounding negative externalities in diverse populations of agents. In AAMAS'18, 2018. To appear. Google Scholar
  29. I. Milchtaich. Network topology and the efficiency of equilibrium. GEB, 57:321-346, 2006. Google Scholar
  30. E. Nikolova and N. Stier-Moses. The burden of risk aversion in mean-risk selfish routing. In EC, pages 489-506, 2015. Google Scholar
  31. Ira Pohl. Heuristic search viewed as path finding in a graph. Artificial intelligence, 1(3-4):193-204, 1970. Google Scholar
  32. N. Robertson and P. Seymour. Graph minors. II. algorithmic aspects of tree-width. Journal of algorithms, 7(3):309-322, 1986. Google Scholar
  33. N. Robertson and P. Seymour. Graph minors. xx. wagner’s conjecture. Journal of Combinatorial Theory, Series B, 92(2):325-357, 2004. Google Scholar
  34. M. Rowland, A. Pacchiano, and A. Weller. Conditions beyond treewidth for tightness of higher-order lp relaxations. In AI and Statistics, pages 10-18, 2017. Google Scholar
  35. M. Safari. D-width: A more natural measure for directed tree width. In MFCS, pages 745-756. Springer, 2005. Google Scholar
  36. C. Shannon. The synthesis of two-terminal switching circuits. Bell Labs Technical Journal, 28(1):59-98, 1949. Google Scholar
  37. K. Takamizawa, T. Nishizeki, and N. Saito. Linear-time computability of combinatorial problems on series-parallel graphs. JACM, 29(3):623-641, 1982. Google Scholar
  38. P. Tang, Y. Teng, Z. Wang, S. Xiao, and Y. Xu. Computational issues in time-inconsistent planning. In AAAI, pages 3665-3671, 2017. Google Scholar
  39. J. Vygen. NP-completeness of some edge-disjoint paths problems. Discrete Applied Mathematics, 61(1):83-90, 1995. Google Scholar
  40. K. Wagner. Über eine eigenschaft der ebenen komplexe. Mathematische Annalen, 114(1):570-590, 1937. Google Scholar
  41. Z. Wang, J. Zhang, J. Feng, and Z. Chen. Knowledge graph embedding by translating on hyperplanes. In AAAI, pages 1112-1119, 2014. 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 About DROPS Imprint Privacy Contact