Document Open Access Logo

On the Fine-Grained Complexity of Least Weight Subsequence in Multitrees and Bounded Treewidth DAGs

Author Jiawei Gao

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2019.16.pdf
  • Filesize: 0.62 MB
  • 17 pages

Document Identifiers

Author Details

Jiawei Gao
  • University of California, San Diego, CA, USA

Funding

Work supported by a Simons Investigator Award from the Simons Foundation.

Acknowledgements

I sincerely thank Russell Impagliazzo for his guidance and advice on this paper. I would like to thank Marco Carmosino and Jessica Sorrell for helpful comments. Also I would like to thank the anonymous reviewers for comments on an earlier version of this paper.

Cite AsGet BibTex

Jiawei Gao. On the Fine-Grained Complexity of Least Weight Subsequence in Multitrees and Bounded Treewidth DAGs. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.IPEC.2019.16

Abstract

This paper introduces a new technique that generalizes previously known fine-grained reductions from linear structures to graphs. Least Weight Subsequence (LWS) [Hirschberg and Larmore, 1987] is a class of highly sequential optimization problems with form F(j) = min_{i < j} [F(i) + c_{i,j}] . They can be solved in quadratic time using dynamic programming, but it is not known whether these problems can be solved faster than n^{2-o(1)} time. Surprisingly, each such problem is subquadratic time reducible to a highly parallel, non-dynamic programming problem [Marvin Künnemann et al., 2017]. In other words, if a "static" problem is faster than quadratic time, so is an LWS problem. For many instances of LWS, the sequential versions are equivalent to their static versions by subquadratic time reductions. The previous result applies to LWS on linear structures, and this paper extends this result to LWS on paths in sparse graphs, the Least Weight Subpath (LWSP) problems. When the graph is a multitree (i.e. a DAG where any pair of vertices can have at most one path) or when the graph is a DAG whose underlying undirected graph has constant treewidth, we show that LWSP on this graph is still subquadratically reducible to their corresponding static problems. For many instances, the graph versions are still equivalent to their static versions. Moreover, this paper shows that if we can decide a property of form Exists x Exists y P(x,y) in subquadratic time, where P is a quickly checkable property on a pair of elements, then on these classes of graphs, we can also in subquadratic time decide whether there exists a pair x,y in the transitive closure of the graph that also satisfy P(x,y).

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • fine-grained complexity
  • dynamic programming
  • graph reachability

Metrics

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

Related Versions

References

  1. Amir Abboud, Arturs Backurs, Karl Bringmann, and Marvin Künnemann. Fine-grained complexity of analyzing compressed data: Quantifying improvements over decompress-and-solve. In Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, pages 192-203. IEEE, 2017. Google Scholar
  2. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 59-78. IEEE, 2015. Google Scholar
  3. Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay. SETH-based lower bounds for subset sum and bicriteria path. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 41-57. SIAM, 2019. Google Scholar
  4. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1681-1697. SIAM, 2014. Google Scholar
  5. Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 375-388. ACM, 2016. Google Scholar
  6. Amir Abboud and Kevin Lewi. Exact weight subgraphs and the k-sum conjecture. In International Colloquium on Automata, Languages, and Programming, pages 1-12. Springer, 2013. Google Scholar
  7. Amir Abboud, Ryan Williams, and Huacheng Yu. More applications of the polynomial method to algorithm design. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 218-230. SIAM, 2015. Google Scholar
  8. Amir Abboud, Virginia Vassilevska Williams, and Joshua Wang. Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete Algorithms, pages 377-391. SIAM, 2016. Google Scholar
  9. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In International Colloquium on Automata, Languages, and Programming, pages 39-51. Springer, 2014. Google Scholar
  10. Udit Agarwal and Vijaya Ramachandran. Fine-grained Complexity for Sparse Graphs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, pages 239-252, New York, NY, USA, 2018. ACM. URL: https://doi.org/10.1145/3188745.3188888.
  11. Alok Aggarwal, Baruch Schieber, and Takeshi Tokuyama. Finding a minimum-weight k-link path in graphs with the concave Monge property and applications. Discrete & Computational Geometry, 12(3):263-280, 1994. Google Scholar
  12. Alfred V Aho and Jeffrey D Ullman. Universality of data retrieval languages. In Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, pages 110-119. ACM, 1979. Google Scholar
  13. Eric Allender and Klaus-Jörn Lange. StUSPACE (log n) ⊆ DSPACE (log² n/log log n). In International Symposium on Algorithms and Computation, pages 193-202. Springer, 1996. Google Scholar
  14. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 51-58. ACM, 2015. Google Scholar
  15. Arturs Backurs and Piotr Indyk. Which regular expression patterns are hard to match? In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 457-466. IEEE, 2016. Google Scholar
  16. Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Towards tight approximation bounds for graph diameter and eccentricities. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 267-280. ACM, 2018. Google Scholar
  17. Hans L Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on computing, 25(6):1305-1317, 1996. Google Scholar
  18. Karl Bringmann. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 661-670. IEEE, 2014. Google Scholar
  19. Karl Bringmann, Allan Grønlund, and Kasper Green Larsen. A dichotomy for regular expression membership testing. In Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, pages 307-318. IEEE, 2017. Google Scholar
  20. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on, pages 79-97. IEEE, 2015. Google Scholar
  21. Karl Bringmann and Marvin Künnemann. Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds. International Journal of Computational Geometry & Applications, 27(01n02):85-119, 2017. Google Scholar
  22. Karl Bringmann and Wolfgang Mulzer. Approximability of the discrete Fréchet distance. Journal of Computational Geometry, 7(2):46-76, 2015. Google Scholar
  23. Timothy M Chan and Ryan Williams. Deterministic APSP, Orthogonal Vectors, and More: Quickly derandomizing Razborov-Smolensky. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1246-1255. SIAM, 2016. Google Scholar
  24. S.C. Chen, J.Y. Wu, G.S. Huang, and R.C.T. Lee. Finding a Longest Increasing Subsequence on a Galled Tree. In the 28th Workshop on Combinatorial Mathematics and Computation Theory, Penghu, Taiwan, 2011. Google Scholar
  25. Michael L Fredman. On computing the length of longest increasing subsequences. Discrete Mathematics, 11(1):29-35, 1975. Google Scholar
  26. Zvi Galil and Kunsoo Park. A linear-time algorithm for concave one-dimensional dynamic programming. Information Processing Letters, 33(6):309-311, 1990. URL: https://doi.org/10.1016/0020-0190(90)90215-J.
  27. Jiawei Gao and Russell Impagliazzo. The Fine-Grained Complexity of Strengthenings of First-Order Logic. Electronic Colloquium on Computational Complexity (ECCC), 26:9, 2019. URL: https://eccc.weizmann.ac.il/report/2019/009.
  28. Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and Ryan Williams. Completeness for First-order Properties on Sparse Structures with Algorithmic Applications. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '17, pages 2162-2181, 2017. Google Scholar
  29. Jerrold R Griggs, Wei-Tian Li, and Linyuan Lu. Diamond-free families. Journal of Combinatorial Theory, Series A, 119(2):310-322, 2012. Google Scholar
  30. Daniel S Hirschberg and Lawrence L Larmore. The least weight subsequence problem. SIAM Journal on Computing, 16(4):628-638, 1987. Google Scholar
  31. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  32. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  33. Thor Johnson, Neil Robertson, Paul D Seymour, and Robin Thomas. Directed tree-width. Journal of Combinatorial Theory, Series B, 82(1):138-154, 2001. Google Scholar
  34. Donald E Knuth and Michael F Plass. Breaking paragraphs into lines. Software: Practice and Experience, 11(11):1119-1184, 1981. Google Scholar
  35. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3SUM conjecture. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 1272-1287. SIAM, 2016. Google Scholar
  36. Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the Fine-Grained Complexity of One-Dimensional Dynamic Programming. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1-21:15, 2017. Google Scholar
  37. Leonid Libkin. Elements of finite model theory. Springer Science & Business Media, 2013. Google Scholar
  38. Guan-Yu Lin, Jia jie Liu, and Yue-Li Wang. Finding a Longest Increasing Subsequence from the Paths in a Complete Bipartite Graph. In Proceedings of the 29th Workshop on Combinatorial Mathematics and Computation Theory, 2012. Google Scholar
  39. Andrea Lincoln, Virginia Vassilevska Williams, and Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1236-1252. Society for Industrial and Applied Mathematics, 2018. Google Scholar
  40. Neil Robertson and Paul D Seymour. Graph minors. III. Planar tree-width. Journal of Combinatorial Theory, Series B, 36(1):49-64, 1984. Google Scholar
  41. Neil Robertson and P.D Seymour. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7(3):309-322, 1986. URL: https://doi.org/10.1016/0196-6774(86)90023-4.
  42. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 515-524. ACM, 2013. Google Scholar
  43. Baruch Schieber. Computing a minimum weightk-link path in graphs with the concave monge property. Journal of Algorithms, 29(2):204-222, 1998. Google Scholar
  44. Larry Joseph Stockmeyer. The complexity of decision problems in automata theory and logic. PhD thesis, Massachusetts Institute of Technology, 1974. Google Scholar
  45. Moshe Y Vardi. The complexity of relational query languages. In Proceedings of the fourteenth annual ACM symposium on Theory of computing, pages 137-146. ACM, 1982. Google Scholar
  46. Robert Wilber. The concave least-weight subsequence problem revisited. Journal of Algorithms, 9(3):418-425, 1988. Google Scholar
  47. Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theoretical Computer Science, 348(2):357-365, 2005. Google Scholar
  48. Ryan Williams. Faster decision of first-order graph properties. In Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), page 80. ACM, 2014. Google Scholar
  49. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on, pages 645-654. IEEE, 2010. Google Scholar
  50. F Frances Yao. Efficient dynamic programming using quadrangle inequalities. In Proceedings of the twelfth annual ACM symposium on Theory of computing, pages 429-435. ACM, 1980. 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