{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T00:40:36Z","timestamp":1776127236620,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,12,27]],"date-time":"2021-12-27T00:00:00Z","timestamp":1640563200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,12,27]],"date-time":"2021-12-27T00:00:00Z","timestamp":1640563200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"crossref","award":["314528"],"award-info":[{"award-number":["314528"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["819416"],"award-info":[{"award-number":["819416"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA-01\/2017-18"],"award-info":[{"award-number":["DST\/SJF\/MSA-01\/2017-18"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,8]]},"abstract":"Abstract<\/jats:title>We initiate the parameterized complexity study of minimum t<\/jats:italic>-spanner problems on directed graphs. For a positive integer t<\/jats:italic>, a multiplicative t<\/jats:italic>-spanner of a (directed) graph G<\/jats:italic> is a spanning subgraph H<\/jats:italic> such that the distance between any two vertices in H<\/jats:italic> is at most t<\/jats:italic> times the distance between these vertices in G<\/jats:italic>, that is, H<\/jats:italic> keeps the distances in G<\/jats:italic> up to the distortion (or stretch) factor t<\/jats:italic>. An additive t<\/jats:italic>-spanner is defined as a spanning subgraph that keeps the distances up to the additive distortion parameter t<\/jats:italic>, that is, the distances in H<\/jats:italic> and G<\/jats:italic> differ by at most t<\/jats:italic>. The task of Directed Multiplicative Spanner<\/jats:sc> is, given a directed graph G<\/jats:italic> with m<\/jats:italic> arcs and positive integers t<\/jats:italic> and k<\/jats:italic>, decide whether G<\/jats:italic> has a multiplicative t<\/jats:italic>-spanner with at most $$m-k$$<\/jats:tex-math>\n \n m<\/mml:mi>\n -<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> arcs. Similarly, Directed Additive Spanner<\/jats:sc> asks whether G<\/jats:italic> has an additive t<\/jats:italic>-spanner with at most $$m-k$$<\/jats:tex-math>\n \n m<\/mml:mi>\n -<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> arcs. We show that (i)\u00a0Directed Multiplicative Spanner<\/jats:sc> admits a polynomial kernel of size $$\\mathcal {O}(k^4t^5)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n k<\/mml:mi>\n 4<\/mml:mn>\n <\/mml:msup>\n \n t<\/mml:mi>\n 5<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and can be solved in randomized $$(4t)^k\\cdot n^{\\mathcal {O}(1)}$$<\/jats:tex-math>\n \n \n \n (<\/mml:mo>\n 4<\/mml:mn>\n t<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n k<\/mml:mi>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time, (ii)\u00a0the weighted variant of Directed Multiplicative Spanner<\/jats:sc> can be solved in $$k^{2k}\\cdot n^{\\mathcal {O}(1)}$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n \n 2<\/mml:mn>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n \u00b7<\/mml:mo>\n \n n<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time on directed acyclic graphs, (iii)\u00a0Directed Additive Spanner<\/jats:sc> is $${{\\,\\mathrm{\\mathsf{W}}\\,}}[1]$$<\/jats:tex-math>\n \n \n \n W<\/mml:mi>\n \n <\/mml:mrow>\n [<\/mml:mo>\n 1<\/mml:mn>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard when parameterized by k<\/jats:italic> for every fixed $$t\\ge 1$$<\/jats:tex-math>\n \n t<\/mml:mi>\n \u2265<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> even when the input graphs are restricted to be directed acyclic graphs. The latter claim contrasts with the recent result of Kobayashi from STACS 2020 that the problem for undirected graphs is $${{\\,\\mathrm{\\mathsf{FPT}}\\,}}$$<\/jats:tex-math>\n \n \n FPT<\/mml:mi>\n \n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> when parameterized by t<\/jats:italic> and k<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s00453-021-00911-x","type":"journal-article","created":{"date-parts":[[2021,12,27]],"date-time":"2021-12-27T11:05:25Z","timestamp":1640603125000},"page":"2292-2308","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Parameterized Complexity of Directed Spanner Problems"],"prefix":"10.1007","volume":"84","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2619-2990","authenticated-orcid":false,"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[]},{"given":"William","family":"Lochet","sequence":"additional","affiliation":[]},{"given":"Pranabendu","family":"Misra","sequence":"additional","affiliation":[]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[]},{"given":"Roohani","family":"Sharma","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,12,27]]},"reference":[{"key":"911_CR1","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.cosrev.2020.100253","volume":"37","author":"AR Ahmed","year":"2020","unstructured":"Ahmed, A.R., Bodwin, G., Sahneh, F.D., Hamm, K., Jebelli, M.J.L., Kobourov, S.G., Spence, R.: Graph spanners: A tutorial review. Comput. Sci. Rev. 37, 100\u2013252 (2020). https:\/\/doi.org\/10.1016\/j.cosrev.2020.100253","journal-title":"Comput. Sci. Rev."},{"issue":"2","key":"911_CR2","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0166-218X(94)90073-6","volume":"48","author":"L Cai","year":"1994","unstructured":"Cai, L.: NP-completeness of minimum spanner problems. Discret. Appl. Math. 48(2), 187\u2013194 (1994). https:\/\/doi.org\/10.1016\/0166-218X(94)90073-6","journal-title":"Discret. Appl. Math."},{"key":"911_CR3","doi-asserted-by":"publisher","unstructured":"Cai, L., Chan, S.M., Chan, S.O.: Random separation: A new method for solving fixed-cardinality optimization problems. In: Parameterized and Exact Computation, Second International Workshop, IWPEC 2006, Z\u00fcrich, Switzerland, September 13-15, 2006, Proceedings. Lecture Notes in Computer Science, vol. 4169, pp. 239\u2013250. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11847250_22","DOI":"10.1007\/11847250_22"},{"key":"911_CR4","doi-asserted-by":"publisher","unstructured":"Chlamt\u00e1c, E., Dinitz, M., Kortsarz, G., Laekhanukit, B.: Approximating spanners and directed steiner forest: Upper and lower bounds. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pp. 534\u2013553. SIAM (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.34","DOI":"10.1137\/1.9781611974782.34"},{"key":"911_CR5","doi-asserted-by":"publisher","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"key":"911_CR6","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of parameterized complexity. Texts in computer science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of parameterized complexity. Texts in computer science. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1"},{"issue":"4","key":"911_CR7","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1007\/s00224-006-1266-2","volume":"41","author":"M Elkin","year":"2007","unstructured":"Elkin, M., Peleg, D.: The hardness of approximating spanner problems. Theory Comput. Syst. 41(4), 691\u2013729 (2007). https:\/\/doi.org\/10.1007\/s00224-006-1266-2","journal-title":"Theory Comput. Syst."},{"key":"911_CR8","first-page":"515","volume-title":"Kernelization: Theory of parameterized preprocessing","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of parameterized preprocessing, p. 515. Cambridge University Press, Cambridge (2019)"},{"key":"911_CR9","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman & Co., United States (1979)"},{"key":"911_CR10","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/j.tcs.2018.06.031","volume":"746","author":"Y Kobayashi","year":"2018","unstructured":"Kobayashi, Y.: NP-hardness and fixed-parameter tractability of the minimum spanner problem. Theor. Comput. Sci. 746, 88\u201397 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2018.06.031","journal-title":"Theor. Comput. Sci."},{"key":"911_CR11","doi-asserted-by":"publisher","unstructured":"Kobayashi, Y.: An FPT algorithm for minimum additive spanner problem. In: Paul, C., Bl\u00e4ser, M. (eds.) 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, March 10-13, 2020, Montpellier, France. LIPIcs, vol. 154, pp. 11\u201311116. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.11","DOI":"10.4230\/LIPIcs.STACS.2020.11"},{"issue":"3","key":"911_CR12","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/s00453-001-0021-y","volume":"30","author":"G Kortsarz","year":"2001","unstructured":"Kortsarz, G.: On the hardness of approximating spanners. Algorithmica 30(3), 432\u2013450 (2001). https:\/\/doi.org\/10.1007\/s00453-001-0021-y","journal-title":"Algorithmica"},{"key":"911_CR13","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1142\/S0129626491000197","volume":"1","author":"AL Liestman","year":"1991","unstructured":"Liestman, A.L., Shermer, T.C.: Additive spanners for hypercubes. Parallel Process. Lett. 1, 35\u201342 (1991). https:\/\/doi.org\/10.1142\/S0129626491000197","journal-title":"Parallel Process. Lett."},{"issue":"4","key":"911_CR14","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/net.3230230417","volume":"23","author":"AL Liestman","year":"1993","unstructured":"Liestman, A.L., Shermer, T.C.: Additive graph spanners. Networks 23(4), 343\u2013363 (1993). https:\/\/doi.org\/10.1002\/net.3230230417","journal-title":"Networks"},{"key":"911_CR15","doi-asserted-by":"publisher","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pp. 182\u2013191. IEEE Computer Society (1995). https:\/\/doi.org\/10.1109\/SFCS.1995.492475","DOI":"10.1109\/SFCS.1995.492475"},{"issue":"1","key":"911_CR16","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph spanners. J. Graph Theor. 13(1), 99\u2013116 (1989). https:\/\/doi.org\/10.1002\/jgt.3190130114","journal-title":"J. Graph Theor."},{"issue":"4","key":"911_CR17","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Comput. 18(4), 740\u2013747 (1989). https:\/\/doi.org\/10.1137\/0218050","journal-title":"SIAM J. Comput."},{"issue":"3","key":"911_CR18","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/1367064.1367069","volume":"4","author":"L Roditty","year":"2008","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Roundtrip spanners and roundtrip routing in directed graphs. ACM Trans. Algorithms 4(3), 29\u201312917 (2008). https:\/\/doi.org\/10.1145\/1367064.1367069","journal-title":"ACM Trans. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00911-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00911-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00911-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T13:10:40Z","timestamp":1658409040000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00911-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,27]]},"references-count":18,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["911"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00911-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,27]]},"assertion":[{"value":"9 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 December 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}