{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T20:14:00Z","timestamp":1776802440748,"version":"3.51.2"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T00:00:00Z","timestamp":1770249600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T00:00:00Z","timestamp":1770249600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"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"}]},{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["314528"],"award-info":[{"award-number":["314528"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We examine the possibility of approximating\n                    <jats:sc>Maximum Vertex-Disjoint Shortest Paths<\/jats:sc>\n                    . In this problem, the input is an edge-weighted (directed or undirected)\n                    <jats:italic>n<\/jats:italic>\n                    -vertex graph\n                    <jats:italic>G<\/jats:italic>\n                    along with\n                    <jats:italic>k<\/jats:italic>\n                    \u00a0terminal pairs\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$(s_1,t_1),(s_2,t_2),\\ldots ,(s_k,t_k)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mrow>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:msub>\n                                <mml:mi>s<\/mml:mi>\n                                <mml:mn>1<\/mml:mn>\n                              <\/mml:msub>\n                              <mml:mo>,<\/mml:mo>\n                              <mml:msub>\n                                <mml:mi>t<\/mml:mi>\n                                <mml:mn>1<\/mml:mn>\n                              <\/mml:msub>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mrow>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:msub>\n                                <mml:mi>s<\/mml:mi>\n                                <mml:mn>2<\/mml:mn>\n                              <\/mml:msub>\n                              <mml:mo>,<\/mml:mo>\n                              <mml:msub>\n                                <mml:mi>t<\/mml:mi>\n                                <mml:mn>2<\/mml:mn>\n                              <\/mml:msub>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mo>\u2026<\/mml:mo>\n                            <mml:mo>,<\/mml:mo>\n                            <mml:mrow>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:msub>\n                                <mml:mi>s<\/mml:mi>\n                                <mml:mi>k<\/mml:mi>\n                              <\/mml:msub>\n                              <mml:mo>,<\/mml:mo>\n                              <mml:msub>\n                                <mml:mi>t<\/mml:mi>\n                                <mml:mi>k<\/mml:mi>\n                              <\/mml:msub>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . The task is to connect as many terminal pairs as possible by pairwise vertex-disjoint paths such that each path is a shortest path between the respective terminals. Our work is anchored in the recent breakthrough by Lochet [SODA \u201921], which demonstrates the polynomial-time solvability of the problem for a fixed value of\n                    <jats:italic>k<\/jats:italic>\n                    . Lochet\u2019s result implies the existence of a polynomial-time\n                    <jats:italic>ck<\/jats:italic>\n                    -approximation for\n                    <jats:sc>Maximum Vertex-Disjoint Shortest Paths<\/jats:sc>\n                    , where\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$c \\le 1$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>c<\/mml:mi>\n                            <mml:mo>\u2264<\/mml:mo>\n                            <mml:mn>1<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is a constant. (One can guess 1\/\n                    <jats:italic>c<\/jats:italic>\n                    terminal pairs to connect in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$k^{O({1}\/{c})}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msup>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mrow>\n                              <mml:mi>O<\/mml:mi>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:mn>1<\/mml:mn>\n                              <mml:mo>\/<\/mml:mo>\n                              <mml:mi>c<\/mml:mi>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:msup>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    \u00a0time and then utilize Lochet\u2019s algorithm to compute the solution in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$n^{f({1}\/{c})}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msup>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mrow>\n                              <mml:mi>f<\/mml:mi>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:mn>1<\/mml:mn>\n                              <mml:mo>\/<\/mml:mo>\n                              <mml:mi>c<\/mml:mi>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:msup>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    \u00a0time.) Our first result suggests that this approximation algorithm is, in a sense, the best we can hope for. More precisely, assuming the gap-ETH, we exclude the existence of an\u00a0\n                    <jats:italic>o<\/jats:italic>\n                    (\n                    <jats:italic>k<\/jats:italic>\n                    )-approximation within\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$f(k){{\\,\\textrm{poly}\\,}}(n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>f<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>k<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                            <mml:mrow>\n                              <mml:mspace\/>\n                              <mml:mtext>poly<\/mml:mtext>\n                              <mml:mspace\/>\n                            <\/mml:mrow>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    \u00a0time for any function\n                    <jats:italic>f<\/jats:italic>\n                    that only depends on\n                    <jats:italic>k<\/jats:italic>\n                    . Our second result demonstrates the infeasibility of achieving an approximation ratio of\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$m^{{1}\/{2}-\\varepsilon }$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msup>\n                            <mml:mi>m<\/mml:mi>\n                            <mml:mrow>\n                              <mml:mn>1<\/mml:mn>\n                              <mml:mo>\/<\/mml:mo>\n                              <mml:mn>2<\/mml:mn>\n                              <mml:mo>-<\/mml:mo>\n                              <mml:mi>\u03b5<\/mml:mi>\n                            <\/mml:mrow>\n                          <\/mml:msup>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    in polynomial time, unless P\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$=$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mo>=<\/mml:mo>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    NP. We also show that this bound is tight by providing a simple\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\sqrt{\\ell }$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msqrt>\n                            <mml:mi>\u2113<\/mml:mi>\n                          <\/mml:msqrt>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -approximation algorithm, where\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\ell $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u2113<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    is the number of edges in all paths of an optimal solution. Additionally, we establish that\n                    <jats:sc>Maximum Vertex-Disjoint Shortest Paths<\/jats:sc>\n                    \u00a0can be solved in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$2^{O(\\ell )} {{\\,\\textrm{poly}\\,}}(n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:msup>\n                              <mml:mn>2<\/mml:mn>\n                              <mml:mrow>\n                                <mml:mi>O<\/mml:mi>\n                                <mml:mo>(<\/mml:mo>\n                                <mml:mi>\u2113<\/mml:mi>\n                                <mml:mo>)<\/mml:mo>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mrow>\n                              <mml:mspace\/>\n                              <mml:mtext>poly<\/mml:mtext>\n                              <mml:mspace\/>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:mi>n<\/mml:mi>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    time, but does not admit a polynomial kernel in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\ell $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u2113<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . Moreover, it cannot be solved in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$2^{o(\\ell )}{{\\,\\textrm{poly}\\,}}(n)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:msup>\n                              <mml:mn>2<\/mml:mn>\n                              <mml:mrow>\n                                <mml:mi>o<\/mml:mi>\n                                <mml:mo>(<\/mml:mo>\n                                <mml:mi>\u2113<\/mml:mi>\n                                <mml:mo>)<\/mml:mo>\n                              <\/mml:mrow>\n                            <\/mml:msup>\n                            <mml:mrow>\n                              <mml:mspace\/>\n                              <mml:mtext>poly<\/mml:mtext>\n                              <mml:mspace\/>\n                            <\/mml:mrow>\n                            <mml:mrow>\n                              <mml:mo>(<\/mml:mo>\n                              <mml:mi>n<\/mml:mi>\n                              <mml:mo>)<\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    time under ETH. Our hardness results hold for undirected graphs with unit weights, while our positive results extend to scenarios where the input graph is directed and features arbitrary (non-negative) edge weights.\n                  <\/jats:p>","DOI":"10.1007\/s00224-025-10252-9","type":"journal-article","created":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T09:02:50Z","timestamp":1770282170000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths"],"prefix":"10.1007","volume":"70","author":[{"given":"Matthias","family":"Bentert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,5]]},"reference":[{"key":"10252_CR1","doi-asserted-by":"crossref","unstructured":"Bentert, M., Fomin, F.V., Golovach, P.A.: Tight approximation and kernelization bounds for vertex-disjoint shortest paths. In: Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science (STACS), pp. 17:1\u201317:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2025)","DOI":"10.1007\/s00224-025-10252-9"},{"issue":"1","key":"10252_CR2","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"RM Karp","year":"1975","unstructured":"Karp, R.M.: On the computational complexity of combinatorial problems. Networks 5(1), 45\u201368 (1975)","journal-title":"Networks"},{"issue":"1","key":"10252_CR3","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII: The disjoint paths problem. J. Combin. Theory Ser. B 63(1), 65\u2013110 (1995)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"2","key":"10252_CR4","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/S0166-218X(97)00121-2","volume":"85","author":"T Eilam-Tzoreff","year":"1998","unstructured":"Eilam-Tzoreff, T.: The disjoint shortest paths problem. Discret. Appl. Math. 85(2), 113\u2013138 (1998)","journal-title":"Discret. Appl. Math."},{"key":"10252_CR5","doi-asserted-by":"crossref","unstructured":"Lochet, W.: A polynomial time algorithm for the $$k$$-disjoint shortest paths problem. In: Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 169\u2013178. SIAM (2021)","DOI":"10.1137\/1.9781611976465.12"},{"issue":"3","key":"10252_CR6","doi-asserted-by":"publisher","first-page":"1674","DOI":"10.1137\/22M1527398","volume":"37","author":"M Bentert","year":"2023","unstructured":"Bentert, M., Nichterlein, A., Renken, M., Zschoche, P.: Using a geometric lens to find $$k$$-disjoint shortest paths. SIAM J. Discret. Math. 37(3), 1674\u20131703 (2023)","journal-title":"SIAM J. Discret. Math."},{"key":"10252_CR7","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J.E., Wyllie, J.: The directed subgraph homeomorphism problem. Theoret. Comput. Sci. 10, 111\u2013121 (1980)","journal-title":"Theoret. Comput. Sci."},{"key":"10252_CR8","unstructured":"Berczi, K., Kobayashi, Y.: The directed disjoint shortest paths problem. In: Proceedings of the 25th Annual European Symposium on Algorithms (ESA), pp. 13:1\u201313:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"key":"10252_CR9","doi-asserted-by":"crossref","unstructured":"Chitnis, R., Thomas, S., Wirth, A.: Lower bounds for approximate (& exact) $$k$$-disjoint-shortest-paths. In: Proceedings of the 22nd International Workshop on Approximation and Online Algorithms (WAOA), pp. 46\u201360. Springer (2024)","DOI":"10.1007\/978-3-031-81396-2_4"},{"key":"10252_CR10","unstructured":"Kleinberg, J.M.: Approximation algorithms for disjoint paths problems. PhD thesis, Massachusetts Institute of Technology (1996)"},{"issue":"1","key":"10252_CR11","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/s10107-002-0370-6","volume":"99","author":"SG Kolliopoulos","year":"2004","unstructured":"Kolliopoulos, S.G., Stein, C.: Approximating disjoint-path problems using packing integer programs. Math. Program. 99(1), 63\u201387 (2004)","journal-title":"Math. Program."},{"key":"10252_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2021.v017a006","volume":"17","author":"J Chuzhoy","year":"2021","unstructured":"Chuzhoy, J., Kim, D.H.K., Nimavat, R.: Almost polynomial hardness of node-disjoint paths in grids. Theory Comput. 17, 1\u201357 (2021)","journal-title":"Theory Comput."},{"issue":"2","key":"10252_CR13","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1137\/17M1146580","volume":"51","author":"J Chuzhoy","year":"2022","unstructured":"Chuzhoy, J., Kim, D.H.K., Nimavat, R.: New hardness results for routing on disjoint paths. SIAM J. Comput. 51(2), 189\u2013237 (2022)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10252_CR14","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1016\/S0022-0000(03)00066-7","volume":"67","author":"V Guruswami","year":"2003","unstructured":"Guruswami, V., Khanna, S., Rajaraman, R., Shepherd, F.B., Yannakakis, M.: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci. 67(3), 473\u2013496 (2003)","journal-title":"J. Comput. Syst. Sci."},{"key":"10252_CR15","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Li, S.: A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2. J. ACM 63(5), 45:1\u201345:51 (2016)","DOI":"10.1145\/2893472"},{"key":"10252_CR16","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, W. H (1979)"},{"key":"10252_CR17","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"10252_CR18","volume-title":"Kernelization","author":"FV Fomin","year":"2019","unstructured":"Fomin, F.V., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization. Cambridge University Press, Cambridge (2019)"},{"issue":"2","key":"10252_CR19","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-sat. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"10252_CR20","unstructured":"Dinur, I.: Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity (2016)"},{"key":"10252_CR21","unstructured":"Manurangsi, P., Raghavendra, P.: A birthday repetition theorem and complexity of approximating dense CSPs. In: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 78:1\u201317:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"key":"10252_CR22","unstructured":"Akmal, S., Williams, V.V., Wein, N.: Detecting disjoint shortest paths in linear time and more. In: Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, ICALP, pp. 9:1\u20139:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024)"},{"key":"10252_CR23","doi-asserted-by":"crossref","unstructured":"Chen, Y., Feng, Y., Laekhanukit, B., Liu, Y.: Simple combinatorial construction of the $$k^{o(1)}$$-lower bound for approximating the parameterized $$k$$-clique. In: Proceedings of the 8th Symposium on Simplicity in Algorithms (SOSA), pp. 263\u2013280. SIAM (2025)","DOI":"10.1137\/1.9781611978315.21"},{"key":"10252_CR24","unstructured":"Karthik C. S., Khot, S.: Almost polynomial factor inapproximability for parameterized $$k$$-clique. In: Proceedings of the 37th Computational Complexity Conference (CCC), pp. 6:1\u20136:21. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2022)"},{"issue":"4","key":"10252_CR25","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1137\/18M1166869","volume":"49","author":"P Chalermsook","year":"2020","unstructured":"Chalermsook, P., Cygan, M., Kortsarz, G., Laekhanukit, B., Manurangsi, P., Nanongkai, D., Trevisan, L.: From gap-exponential time hypothesis to fixed parameter tractable inapproximability: Clique, dominating set, and more. SIAM J. Comput. 49(4), 772\u2013810 (2020)","journal-title":"SIAM J. Comput."},{"key":"10252_CR26","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^{1-\\varepsilon }$$. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS), pp. 627\u2013636. IEEE Computer Society (1996)","DOI":"10.1109\/SFCS.1996.548522"},{"issue":"1","key":"10252_CR27","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theory Comput. 3(1), 103\u2013128 (2007)","journal-title":"Theory Comput."},{"issue":"4","key":"10252_CR28","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995)","journal-title":"J. ACM"},{"key":"10252_CR29","doi-asserted-by":"crossref","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS), pp. 182\u2013191. IEEE Computer Society (1995)","DOI":"10.1109\/SFCS.1995.492475"},{"issue":"4","key":"10252_CR30","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10252_CR31","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(84)90081-7","volume":"8","author":"CA Tovey","year":"1984","unstructured":"Tovey, C.A.: A simplified NP-complete satisfiability problem. Discret. Appl. Math. 8(1), 85\u201389 (1984)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"10252_CR32","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329\u2013343 (1982)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10252_CR33","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1137\/0405033","volume":"5","author":"DE Knuth","year":"1992","unstructured":"Knuth, D.E., Raghunathan, A.: The problem of compatible representatives. SIAM J. Discret. Math. 5(3), 422\u2013427 (1992)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"10252_CR34","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1142\/S0218195912500045","volume":"22","author":"M de Berg","year":"2012","unstructured":"de Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. Int. J. Comput. Geom. Appl. 22(3), 187\u2013206 (2012)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"1","key":"10252_CR35","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/120880240","volume":"28","author":"HL Bodlaender","year":"2014","unstructured":"Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discret. Math. 28(1), 277\u2013305 (2014)","journal-title":"SIAM J. Discret. Math."},{"key":"10252_CR36","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Panolan, F., Ramanujan, M.S., Saurabh, S.: Lossy kernelization. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 224\u2013237. ACM (2017)","DOI":"10.1145\/3055399.3055456"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10252-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10252-9","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10252-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T08:42:29Z","timestamp":1776760949000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10252-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,5]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10252"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10252-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,5]]},"assertion":[{"value":"22 April 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 November 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 February 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"5"}}