Document Open Access Logo

Width Notions for Ordering-Related Problems

Authors Emmanuel Arrighi , Henning Fernau , Mateus de Oliveira Oliveira , Petra Wolf

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2020.9.pdf
  • Filesize: 0.61 MB
  • 18 pages

Document Identifiers

Author Details

Emmanuel Arrighi
  • University of Bergen, Norway
Henning Fernau
  • University of Trier, Germany
Mateus de Oliveira Oliveira
  • University of Bergen, Norway
Petra Wolf
  • University of Trier, Germany

Funding

  • Arrighi, Emmanuel: Research Council of Norway (Grant no. 274526), IS-DAAD (Grant no. 309319).
  • Fernau, Henning: DAAD PPP (Grant no. 57525246).
  • de Oliveira Oliveira, Mateus: Trond Mohn Foundation, Research Council of Norway (Grant no. 288761), IS-DAAD (Grant no. 309319).
  • Wolf, Petra: DFG project FE 560/9-1, DAAD PPP (Grant no. 57525246).

Cite AsGet BibTex

Emmanuel Arrighi, Henning Fernau, Mateus de Oliveira Oliveira, and Petra Wolf. Width Notions for Ordering-Related Problems. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FSTTCS.2020.9

Abstract

We are studying a weighted version of a linear extension problem, given some finite partial order ρ, called Completion of an Ordering. While this problem is NP-complete, we show that it lies in FPT when parameterized by the interval width of ρ. This ordering problem can be used to model several ordering problems stemming from diverse application areas, such as graph drawing, computational social choice, or computer memory management. Each application yields a special ρ. We also relate the interval width of ρ to parameterizations such as maximum range that have been introduced earlier in these applications, sometimes improving on parameterized algorithms that have been developed for these parameterizations before. This approach also gives some practical sub-exponential time algorithms for ordering problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
  • Theory of computation → Dynamic programming
  • Mathematics of computing → Combinatorial optimization
Keywords
  • Parameterized algorithms
  • interval width
  • linear extension
  • one-sided crossing minimization
  • Kemeny rank aggregation
  • grouping by swapping

Metrics

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

References

  1. Noga Alon, Daniel Lokshtanov, and Saket Saurabh. Fast FAST. In Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris E. Nikoletseas, and Wolfgang Thomas, editors, Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I, volume 5555 of Lecture Notes in Computer Science, pages 49-58. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-02927-1_6.
  2. J. Bartholdi, III, C. A. Tovey, and M. A. Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6:157-165, 1989. Google Scholar
  3. Oliver Bastert and Christian Matuszewski. Layered drawings of digraphs. In Michael Kaufmann and Dorothea Wagner, editors, Drawing Graphs, Methods and Models (the book grow out of a Dagstuhl Seminar, April 1999), volume 2025 of Lecture Notes in Computer Science, pages 87-120. Springer, 1999. URL: https://doi.org/10.1007/3-540-44969-8_5.
  4. Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice-Hall, 1999. Google Scholar
  5. Nadja Betzler, Michael R. Fellows, Jiong Guo, Rolf Niedermeier, and Frances A. Rosamond. Fixed-parameter algorithms for kemeny rankings. Theor. Comput. Sci., 410(45):4554-4570, 2009. URL: https://doi.org/10.1016/j.tcs.2009.08.033.
  6. Kellogg S. Booth and George S. Lueker. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci., 13(3):335-379, 1976. URL: https://doi.org/10.1016/S0022-0000(76)80045-1.
  7. Vincent Bouchitté and Michel Habib. NP-completeness properties about linear extensions. Order, 4(2):143-154, 1987. Google Scholar
  8. Franz J. Brandenburg and Andreas Gleißner. Ranking chain sum orders. Theor. Comput. Sci., 636:66-76, 2016. URL: https://doi.org/10.1016/j.tcs.2016.05.026.
  9. Franz-Josef Brandenburg, Andreas Gleißner, and Andreas Hofmeier. Comparing and aggregating partial orders with kendall tau distances. Discrete Math., Alg. and Appl., 5(2), 2013. URL: https://doi.org/10.1142/S1793830913600033.
  10. Christoph Buchheim, Angelika Wiegele, and Lanbo Zheng. Exact algorithms for the quadratic linear ordering problem. INFORMS J. Comput., 22(1):168-177, 2010. URL: https://doi.org/10.1287/ijoc.1090.0318.
  11. Olca A. Çakiroglu, Cesim Erten, Ömer Karatas, and Melih Sözdinler. Crossing minimization in weighted bipartite graphs. J. Discrete Algorithms, 7(4):439-452, 2009. URL: https://doi.org/10.1016/j.jda.2008.08.003.
  12. Irène Charon and Olivier Hudry. A survey on the linear ordering problem for weighted or unweighted tournaments. 4OR, 5(1):5-60, 2007. URL: https://doi.org/10.1007/s10288-007-0036-6.
  13. Derek G. Corneil, Barnaby Dalton, and Michel Habib. LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs. SIAM J. Comput., 42(3):792-807, 2013. URL: https://doi.org/10.1137/11083856X.
  14. Derek G. Corneil, Stephan Olariu, and Lorna Stewart. The LBFS structure and recognition of interval graphs. SIAM J. Discret. Math., 23(4):1905-1953, 2009. URL: https://doi.org/10.1137/S0895480100373455.
  15. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  16. Vida Dujmovic, Henning Fernau, and Michael Kaufmann. Fixed parameter algorithms for one-sided crossing minimization revisited. In Giuseppe Liotta, editor, Graph Drawing, 11th International Symposium, GD 2003, Perugia, Italy, September 21-24, 2003, Revised Papers, volume 2912 of Lecture Notes in Computer Science, pages 332-344. Springer, 2003. URL: https://doi.org/10.1007/b94919.
  17. Vida Dujmovic, Henning Fernau, and Michael Kaufmann. Fixed parameter algorithms for one-sided crossing minimization revisited. J. Discrete Algorithms, 6(2):313-323, 2008. Google Scholar
  18. Vida Dujmovic and Sue Whitesides. An efficient fixed parameter tractable algorithm for 1-sided crossing minimization. Algorithmica, 40(1):15-31, 2004. Google Scholar
  19. Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar. Rank aggregation methods for the web. In Vincent Y. Shen, Nobuo Saito, Michael R. Lyu, and Mary Ellen Zurko, editors, Proceedings of the Tenth International World Wide Web Conference, WWW 10, Hong Kong, China, May 1-5, 2001, pages 613-622. ACM, 2001. URL: https://doi.org/10.1145/371920.372165.
  20. Peter Eades and D. Kelly. Heuristics for reducing crossings in 2-layered networks. Ars Combinatoria, 21A:89-98, 1986. Google Scholar
  21. Peter Eades and Nicholas C. Wormald. Edge crossings in drawings of bipartite graphs. Algorithmica, 11(4):379-403, 1994. Google Scholar
  22. Eduard Eiben, Robert Ganian, Kustaa Kangas, and Sebastian Ordyniak. Counting linear extensions: Parameterizations by treewidth. Algorithmica, 81(4):1657-1683, 2019. URL: https://doi.org/10.1007/s00453-018-0496-4.
  23. Henning Fernau. Parameterized Algorithmics: A Graph-Theoretic Approach. Habilitationsschrift, Universität Tübingen, Germany, 2005. Google Scholar
  24. Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Matthias Mnich, Geevarghese Philip, and Saket Saurabh. Ranking and drawing in subexponential time. In Costas S. Iliopoulos and William F. Smyth, editors, Combinatorial Algorithms - 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers, volume 6460 of Lecture Notes in Computer Science, pages 337-348. Springer, 2011. Google Scholar
  25. Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Matthias Mnich, Geevarghese Philip, and Saket Saurabh. Social choice meets graph drawing: How to get subexponential time algorithms for ranking and drawing problems. TSINGHUA SCIENCE AND TECHNOLOGY, 19(4):374-386, 2014. Google Scholar
  26. Peter C. Fishburn. Interval Orders and Interval Graphs. John Wiley, 1985. Google Scholar
  27. Michael Forster. A fast and simple heuristic for constrained two-level crossing reduction. In János Pach, editor, Graph Drawing, 12th International Symposium, GD 2004, New York, NY, USA, September 29 - October 2, 2004, Revised Selected Papers, volume 3383 of Lecture Notes in Computer Science, pages 206-216. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-31843-9_22.
  28. M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. Google Scholar
  29. Paul C Gilmore and Alan J Hoffman. A characterization of comparability graphs and of interval graphs. Canadian Journal of Mathematics, 16:539-548, 1964. Google Scholar
  30. Michel Habib, Ross M. McConnell, Christophe Paul, and Laurent Viennot. Lex-bfs and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing. Theor. Comput. Sci., 234(1-2):59-84, 2000. URL: https://doi.org/10.1016/S0304-3975(97)00241-7.
  31. Michel Habib and Rolf H. Möhring. Treewidth of cocomparability graphs and a new order-theoretic parameter. Order, 11(1):47-60, 1994. Google Scholar
  32. Patrick Healy and Nikola S. Nikolov. Hierarchical drawing algorithms. In Roberto Tamassia, editor, Handbook on Graph Drawing and Visualization, pages 409-453. Chapman and Hall/CRC, 2013. Google Scholar
  33. Wen-Lian Hsu and Tze-Heng Ma. Fast and simple algorithms for recognizing chordal comparability graphs and interval graphs. SIAM J. Comput., 28(3):1004-1020, 1999. URL: https://doi.org/10.1137/S0097539792224814.
  34. Olivier Hudry. NP-hardness results for the aggregation of linear orders into median orders. Annals of Operations Research, 163:63-88, 2008. Google Scholar
  35. Marek Karpinski and Warren Schudy. Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament. In Otfried Cheong, Kyung-Yong Chwa, and Kunsoo Park, editors, Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I, volume 6506 of Lecture Notes in Computer Science, pages 3-14. Springer, 2010. Google Scholar
  36. John G. Kemeny. Mathematics without numbers. Daedalus, 88:571-591, 1959. Google Scholar
  37. Yasuaki Kobayashi, Hirokazu Maruta, Yusuke Nakae, and Hisao Tamaki. A linear edge kernel for two-layer crossing minimization. Theor. Comput. Sci., 554:74-81, 2014. Google Scholar
  38. Yasuaki Kobayashi and Hisao Tamaki. A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization. Algorithmica, 72(3):778-790, 2015. Google Scholar
  39. Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, and Oleg Verbitsky. Interval graphs: Canonical representations in logspace. SIAM J. Comput., 40(5):1292-1315, 2011. URL: https://doi.org/10.1137/10080395X.
  40. Johannes Köbler, Sebastian Kuhnert, and Osamu Watanabe. Interval graph representation with given interval and intersection lengths. J. Discrete Algorithms, 34:108-117, 2015. URL: https://doi.org/10.1016/j.jda.2015.05.011.
  41. Longcheng Liu, Biao Wu, and Enyu Yao. Minimizing the sum cost in linear extensions of a poset. J. Comb. Optim., 21(2):247-253, 2011. URL: https://doi.org/10.1007/s10878-009-9237-6.
  42. Roy Lowrance and Robert A. Wagner. An extension of the string-to-string correction problem. J. ACM, 22(2):177-183, 1975. URL: https://doi.org/10.1145/321879.321880.
  43. B. Monjardet. Tournois et ordres médians pour une opinion. Mathématiques et Sciences humaines, 43:55-73, 1973. Google Scholar
  44. Xavier Muñoz, Walter Unger, and Imrich Vrt'o. One sided crossing minimization is NP-hard for sparse graphs. In Petra Mutzel, Michael Jünger, and Sebastian Leipert, editors, Graph Drawing, 9th International Symposium, GD 2001 Vienna, Austria, September 23-26, 2001, Revised Papers, volume 2265 of Lecture Notes in Computer Science, pages 115-123. Springer, 2001. URL: https://doi.org/10.1007/3-540-45848-4.
  45. Petra Mutzel. Optimization in leveled graphs. In Christodoulos A. Floudas and Panos M. Pardalos, editors, Encyclopedia of Optimization, Second Edition, pages 2813-2820. Springer, 2009. URL: https://doi.org/10.1007/978-0-387-74759-0_483.
  46. Hiroshi Nagamochi. An improved bound on the one-sided minimum crossing number in two-layered drawings. Discret. Comput. Geom., 33(4):569-591, 2005. URL: https://doi.org/10.1007/s00454-005-1168-0.
  47. Itsik Pe'er and Ron Shamir. Realizing interval graphs with size and distance constraints. SIAM J. Discret. Math., 10(4):662-687, 1997. URL: https://doi.org/10.1137/S0895480196306373.
  48. Itsik Pe'er and Ron Shamir. Satisfiability problems on intervals and unit intervals. Theor. Comput. Sci., 175(2):349-372, 1997. URL: https://doi.org/10.1016/S0304-3975(96)00208-3.
  49. Daniel Reidenbach and Markus L. Schmid. Patterns with bounded treewidth. Inf. Comput., 239:87-99, 2014. Google Scholar
  50. Carl Sechen. VLSI placement and global routing using simulated annealing, volume 54. Springer Science & Business Media, 2012. Google Scholar
  51. Narges Simjour. Improved parameterized algorithms for the Kemeny aggregation problem. In Jianer Chen and Fedor V. Fomin, editors, Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, September 10-11, 2009, Revised Selected Papers, volume 5917 of Lecture Notes in Computer Science, pages 312-323. Springer, 2009. Google Scholar
  52. Matthias F. M. Stallmann, Franc Brglez, and Debabrata Ghosh. Heuristics, experimental subjects, and treatment evaluation in bigraph crossing minimization. ACM J. Exp. Algorithmics, 6:8, 2001. URL: https://doi.org/10.1145/945394.945402.
  53. Kozo Sugiyama, Shojiro Tagawa, and Mitsuhiko Toda. Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cybern., 11(2):109-125, 1981. URL: https://doi.org/10.1109/TSMC.1981.4308636.
  54. William T. Trotter. New perspectives on interval orders and interval graphs. In R. A. Bailey, editor, Surveys in Combinatorics, volume 241 of London Mathematical Society Lecture Note Series, pages 237-286. 1997. Google Scholar
  55. D. F. Wong and Edward M. Reingold. Probabilistic analysis of a grouping algorithm. Algorithmica, 6(2):192-206, 1991. URL: https://doi.org/10.1007/BF01759041.
  56. H. P. Young and A. Levenglick. A consistent extension of Condercet’s election principle. SIAM J. Appl. Math., 35(2):285-300, 1978. Google Scholar
  57. Anke van Zuylen and David P. Williamson. Deterministic pivoting algorithms for constrained ranking and clustering problems. Math. Oper. Res., 34(3):594-620, 2009. URL: https://doi.org/10.1287/moor.1090.0385.
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