{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T01:53:24Z","timestamp":1772502804792,"version":"3.50.1"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T00:00:00Z","timestamp":1628726400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T00:00:00Z","timestamp":1628726400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100010583","name":"Universit\u00e4t Konstanz","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100010583","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the <jats:italic>k<\/jats:italic><jats:sc>-Center<\/jats:sc> problem, where the input is a graph <jats:inline-formula><jats:alternatives><jats:tex-math>$$G=(V,E)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>V<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>E<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with positive edge weights and an integer <jats:italic>k<\/jats:italic>, and the goal is to select <jats:italic>k<\/jats:italic> center vertices <jats:inline-formula><jats:alternatives><jats:tex-math>$$C \\subseteq V$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>C<\/mml:mi>\n                    <mml:mo>\u2286<\/mml:mo>\n                    <mml:mi>V<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that the maximum distance from any vertex to the closest center vertex is minimized. In general, this problem is <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathsf {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>NP<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard and cannot be approximated within a factor less than 2. Typical applications of the <jats:italic>k<\/jats:italic><jats:sc>-Center<\/jats:sc> problem can be found in logistics or urban planning and hence, it is natural to study the problem on transportation networks. Common characterizations of such networks are graphs that are (almost) planar or have low doubling dimension, highway dimension or skeleton dimension. It was shown by Feldmann and Marx that <jats:italic>k<\/jats:italic><jats:sc>-Center<\/jats:sc> is <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathsf {W[1]}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>W<\/mml:mi>\n                    <mml:mo>[<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>]<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard on planar graphs of constant doubling dimension when parameterized by the number of centers <jats:italic>k<\/jats:italic>, the highway dimension <jats:inline-formula><jats:alternatives><jats:tex-math>$$hd$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>hd<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and the pathwidth <jats:inline-formula><jats:alternatives><jats:tex-math>$$pw$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>pw<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> (Feldmann and Marx 2020). We extend their result and show that even if we additionally parameterize by the skeleton dimension <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\kappa $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03ba<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the <jats:italic>k<\/jats:italic><jats:sc>-Center<\/jats:sc> problem remains <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathsf {W[1]}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>W<\/mml:mi>\n                    <mml:mo>[<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>]<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard. Moreover, we prove that under the Exponential Time Hypothesis there is no exact algorithm for <jats:italic>k<\/jats:italic><jats:sc>-Center<\/jats:sc> that has runtime <jats:inline-formula><jats:alternatives><jats:tex-math>$$f(k,hd,pw,\\kappa ) \\cdot \\vert V \\vert ^{o(pw+ \\kappa + \\sqrt{k+hd})}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>f<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>k<\/mml:mi>\n                      <mml:mo>,<\/mml:mo>\n                      <mml:mi>h<\/mml:mi>\n                      <mml:mi>d<\/mml:mi>\n                      <mml:mo>,<\/mml:mo>\n                      <mml:mi>p<\/mml:mi>\n                      <mml:mi>w<\/mml:mi>\n                      <mml:mo>,<\/mml:mo>\n                      <mml:mi>\u03ba<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>\u00b7<\/mml:mo>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mo>|<\/mml:mo>\n                        <mml:mi>V<\/mml:mi>\n                        <mml:mo>|<\/mml:mo>\n                      <\/mml:mrow>\n                      <mml:mrow>\n                        <mml:mi>o<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mi>p<\/mml:mi>\n                        <mml:mi>w<\/mml:mi>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:mi>\u03ba<\/mml:mi>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:msqrt>\n                          <mml:mrow>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mo>+<\/mml:mo>\n                            <mml:mi>h<\/mml:mi>\n                            <mml:mi>d<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:msqrt>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for any computable function <jats:italic>f<\/jats:italic>.<\/jats:p>","DOI":"10.1007\/s10878-021-00792-4","type":"journal-article","created":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T12:05:02Z","timestamp":1628769902000},"page":"2762-2781","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["W[1]-hardness of the k-center problem parameterized by the skeleton dimension"],"prefix":"10.1007","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1102-3649","authenticated-orcid":false,"given":"Johannes","family":"Blum","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,12]]},"reference":[{"key":"792_CR1","doi-asserted-by":"publisher","DOI":"10.1145\/2985473","author":"I Abraham","year":"2016","unstructured":"Abraham I, Delling D, Fiat A, Goldberg AV, Werneck RF (2016) Highway dimension and provably efficient shortest path algorithms. J ACM. https:\/\/doi.org\/10.1145\/2985473","journal-title":"J ACM"},{"key":"792_CR2","doi-asserted-by":"publisher","unstructured":"Abraham I, Delling D, Fiat A, Goldberg AV, Werneck RFF (2011) Vc-dimension and shortest path algorithms. In: L. Aceto, M. Henzinger, J. Sgall (eds.) Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP \u201911), Lecture Notes in Computer Science, vol. 6755, pp. 690\u2013699. Springer . https:\/\/doi.org\/10.1007\/978-3-642-22006-7_58","DOI":"10.1007\/978-3-642-22006-7_58"},{"key":"792_CR3","doi-asserted-by":"publisher","unstructured":"Abraham I, Fiat A, Goldberg AV, Werneck RFF (2010) Highway dimension, shortest paths, and provably efficient algorithms. In: M. Charikar (ed.) Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA \u201910), pp. 782\u2013793. SIAM . https:\/\/doi.org\/10.1137\/1.9781611973075.64","DOI":"10.1137\/1.9781611973075.64"},{"key":"792_CR4","doi-asserted-by":"publisher","unstructured":"Becker A, Klein PN, Saulpic D (2018) Polynomial-time approximation schemes for k-center, k-median, and capacitated vehicle routing in bounded highway dimension. In: Y. Azar, H. Bast, G. Herman (eds.) Proceedings of the 26th Annual European Symposium on Algorithms (ESA \u201918), LIPIcs, vol. 112, pp. 8:1\u20138:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik . https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2018.8","DOI":"10.4230\/LIPIcs.ESA.2018.8"},{"key":"792_CR5","doi-asserted-by":"publisher","unstructured":"Blum J (2019) Hierarchy of transportation network parameters and hardness results. In: B.M.P. Jansen, J.A. Telle (eds.) Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC \u201919), LIPIcs, vol. 148, pp. 4:1\u20134:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik . https:\/\/doi.org\/10.4230\/LIPIcs.IPEC.2019.4","DOI":"10.4230\/LIPIcs.IPEC.2019.4"},{"key":"792_CR6","doi-asserted-by":"crossref","unstructured":"Blum J, Storandt S (2018) Scalability of route planning techniques. In: M. de Weerdt, S. Koenig, G. R\u00f6ger, M.T.J. Spaan (eds.) Proceedings of the 28th International Conference on Automated Planning and Scheduling (ICAPS \u201918), pp. 20\u201328. AAAI Press . https:\/\/aaai.org\/ocs\/index.php\/ICAPS\/ICAPS18\/paper\/view\/17741","DOI":"10.1609\/icaps.v28i1.13888"},{"key":"792_CR7","doi-asserted-by":"publisher","unstructured":"Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized Algorithms. Springer . https:\/\/doi.org\/10.1007\/978-3-319-21275-3","DOI":"10.1007\/978-3-319-21275-3"},{"key":"792_CR8","doi-asserted-by":"publisher","unstructured":"Feder T, Greene DH (1988) Optimal algorithms for approximate clustering. In: J. Simon (ed.) Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC \u201988), pp. 434\u2013444. ACM . https:\/\/doi.org\/10.1145\/62212.62255","DOI":"10.1145\/62212.62255"},{"issue":"3","key":"792_CR9","doi-asserted-by":"publisher","first-page":"1031","DOI":"10.1007\/s00453-018-0455-0","volume":"81","author":"AE Feldmann","year":"2019","unstructured":"Feldmann AE (2019) Fixed-parameter approximations for k-center problems in low highway dimension graphs. Algorithmica 81(3):1031\u20131052. https:\/\/doi.org\/10.1007\/s00453-018-0455-0","journal-title":"Algorithmica"},{"issue":"7","key":"792_CR10","doi-asserted-by":"publisher","first-page":"1989","DOI":"10.1007\/s00453-020-00683-w","volume":"82","author":"AE Feldmann","year":"2020","unstructured":"Feldmann AE, Marx D (2020) The parameterized hardness of the k-center problem in transportation networks. Algorithmica 82(7):1989\u20132005. https:\/\/doi.org\/10.1007\/s00453-020-00683-w","journal-title":"Algorithmica"},{"issue":"3","key":"792_CR11","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/5925.5933","volume":"33","author":"DS Hochbaum","year":"1986","unstructured":"Hochbaum DS, Shmoys DB (1986) A unified approach to approximation algorithms for bottleneck problems. J ACM 33(3):533\u2013550. https:\/\/doi.org\/10.1145\/5925.5933","journal-title":"J ACM"},{"key":"792_CR12","doi-asserted-by":"publisher","unstructured":"Kosowski A, Viennot L (2017) Beyond highway dimension: Small distance labels using tree skeletons. In: P.N. Klein (ed.) Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201917), pp. 1462\u20131478. SIAM . https:\/\/doi.org\/10.1137\/1.9781611974782.95","DOI":"10.1137\/1.9781611974782.95"},{"key":"792_CR13","doi-asserted-by":"crossref","unstructured":"Plesn\u00edk J (1980) On the computational complexity of centers locating in a graph. Aplikace matematiky 25(6), 445\u2013452 . https:\/\/dml.cz\/bitstream\/handle\/10338.dmlcz\/103883\/AplMat_25-1980-6_8.pdf","DOI":"10.21136\/AM.1980.103883"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00792-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00792-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00792-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,14]],"date-time":"2022-10-14T20:21:44Z","timestamp":1665778904000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00792-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,12]]},"references-count":13,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["792"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00792-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,12]]},"assertion":[{"value":"2 August 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}