{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T04:23:12Z","timestamp":1744172592189,"version":"3.40.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T00:00:00Z","timestamp":1737590400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T00:00:00Z","timestamp":1737590400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100012957","name":"Friedrich-Schiller-Universit\u00e4t Jena","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100012957","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,3]]},"abstract":"Abstract<\/jats:title>\n An independent set\u00a0S<\/jats:italic> in a graph\u00a0G<\/jats:italic> is k<\/jats:italic>-swap-optimal if there is no independent set\u00a0\n \n $$S'$$<\/jats:tex-math>\n \n \n S<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> such that\u00a0\n \n $$\\varvec{|S'|>|S|}$$<\/jats:tex-math>\n \n \n \n |<\/mml:mo>\n <\/mml:mrow>\n \n S<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n \n |<\/mml:mo>\n ><\/mml:mo>\n |<\/mml:mo>\n S<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and\u00a0\n \n $$\\varvec{|(S'\\setminus S)\\cup (S\\setminus S')|\\le k}$$<\/jats:tex-math>\n \n \n \n |<\/mml:mo>\n <\/mml:mrow>\n \n (<\/mml:mo>\n \n S<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n \\<\/mml:mo>\n S<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u222a<\/mml:mo>\n \n (<\/mml:mo>\n S<\/mml:mi>\n \\<\/mml:mo>\n \n S<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n \n |<\/mml:mo>\n \u2264<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. Motivated by applications in data reduction, we study whether we can determine efficiently if a given vertex\u00a0v<\/jats:italic> is contained in some k<\/jats:italic>-swap-optimal independent set or in all k<\/jats:italic>-swap-optimal independent sets. We show that these problems are NP-hard for constant values of\u00a0k<\/jats:italic> even on graphs with constant maximum degree. Moreover, we show that the problems are\u00a0\n \n $$\\varvec{\\Sigma ^{\\text {P}}_{2}}$$<\/jats:tex-math>\n \n \n \n \u03a3<\/mml:mi>\n 2<\/mml:mn>\n P<\/mml:mtext>\n <\/mml:msubsup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-hard when\u00a0k<\/jats:italic> is not constant, even on graphs of constant maximum degree. We obtain similar hardness results for determining whether an edge is contained in a k<\/jats:italic>-swap optimal max cut. Finally, we consider a certain type of edge-swap neighborhood for the Longest Path<\/jats:sc> problem. We show that for a given edge we can decide in \n \n $$\\varvec{f(\\Delta +k)\\cdot n^{\\mathcal {O}(1)}}$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n \n (<\/mml:mo>\n \u0394<\/mml:mi>\n +<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\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>\n <\/jats:alternatives>\n <\/jats:inline-formula>\u00a0time whether it is in some k<\/jats:italic>-optimal path.<\/jats:p>","DOI":"10.1007\/s00224-024-10205-8","type":"journal-article","created":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T09:53:26Z","timestamp":1737626006000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Can Local Optimality Be Used for Efficient Data Reduction?"],"prefix":"10.1007","volume":"69","author":[{"given":"Christian","family":"Komusiewicz","sequence":"first","affiliation":[]},{"given":"Nils","family":"Morawietz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,23]]},"reference":[{"key":"10205_CR1","doi-asserted-by":"publisher","unstructured":"Bonnet, \u00c9., Iwata, Y., Jansen, B.M.P., Kowalik, L.: Fine-grained complexity of $$k$$-OPT in bounded-degree graphs for solving TSP. In: Bender, M.A., Svensson, O., Herman, G. (eds.) Proceedings of the 27th Annual European Symposium on Algorithms (ESA\u00a0\u201919). LIPIcs, vol. 144, pp. 23\u201312314. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, (2019). https:\/\/doi.org\/10.4230\/LIPICS.ESA.2019.23","DOI":"10.4230\/LIPICS.ESA.2019.23"},{"issue":"3","key":"10205_CR2","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0167-6377(02)00241-9","volume":"31","author":"T Br\u00fcggemann","year":"2003","unstructured":"Br\u00fcggemann, T., Monnot, J., Woeginger, G.J.: Local search for the minimum label spanning tree problem with bounded color classes. Oper. Res. Lett. 31(3), 195\u2013201 (2003). https:\/\/doi.org\/10.1016\/S0167-6377(02)00241-9","journal-title":"Oper. Res. Lett."},{"key":"10205_CR3","doi-asserted-by":"publisher","unstructured":"Cai, S., Su, K., Luo, C., Sattar, A.: NuMVC: An efficient local search algorithm for minimum vertex cover. J. Artif. Intell. Res. 46, 687\u2013716 (2013). https:\/\/doi.org\/10.1613\/JAIR.3907","DOI":"10.1613\/JAIR.3907"},{"issue":"1","key":"10205_CR4","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/S00453-012-9685-8","volume":"67","author":"J Guo","year":"2013","unstructured":"Guo, J., Hartung, S., Niedermeier, R., Such\u00fd, O.: The parameterized complexity of local search for TSP, more refined. Algorithmica 67(1), 89\u2013110 (2013). https:\/\/doi.org\/10.1007\/S00453-012-9685-8","journal-title":"Algorithmica"},{"key":"10205_CR5","unstructured":"Hoos, H.H., St\u00fctzle, T.: Stochastic Local Search: Foundations & Applications. Elsevier \/ Morgan Kaufmann, (2004)"},{"issue":"1","key":"10205_CR6","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"DS Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79\u2013100 (1988). https:\/\/doi.org\/10.1016\/0022-0000(88)90046-3","journal-title":"J. Comput. Syst. Sci."},{"key":"10205_CR7","doi-asserted-by":"publisher","unstructured":"Katzmann, M., Komusiewicz, C.: Systematic exploration of larger local search neighborhoods for the minimum vertex cover problem. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI\u00a0\u201917), pp. 846\u2013852. AAAI Press, (2017). https:\/\/doi.org\/10.1609\/aaai.v31i1.10659","DOI":"10.1609\/aaai.v31i1.10659"},{"issue":"1","key":"10205_CR8","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/J.ORL.2007.02.008","volume":"36","author":"D Marx","year":"2008","unstructured":"Marx, D.: Searching the $$k$$-change neighborhood for TSP is W[1]-hard. Oper. Res. Lett. 36(1), 31\u201336 (2008). https:\/\/doi.org\/10.1016\/J.ORL.2007.02.008","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"10205_CR9","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1016\/J.JCSS.2011.10.003","volume":"78","author":"MR Fellows","year":"2012","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F.A., Saurabh, S., Villanger, Y.: Local search: Is brute-force avoidable? J. Comput. Syst. Sci. 78(3), 707\u2013719 (2012). https:\/\/doi.org\/10.1016\/J.JCSS.2011.10.003","journal-title":"J. Comput. Syst. Sci."},{"key":"10205_CR10","doi-asserted-by":"publisher","unstructured":"Casel, K., Fernau, H., Khosravian Ghadikolaei, M., Monnot, J., Sikora, F.: Extension of vertex cover and independent set in some classes of graphs. In: Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC\u00a0\u201919). Lecture Notes in Computer Science, vol. 11485, pp. 124\u2013136. Springer, (2019). https:\/\/doi.org\/10.1007\/978-3-030-17402-6_11","DOI":"10.1007\/978-3-030-17402-6_11"},{"key":"10205_CR11","doi-asserted-by":"publisher","unstructured":"Ghadikolaei, M.K., Melissinos, N., Monnot, J., Pagourtzis, A.: Extension and its price for the connected vertex cover problem. Theor. Comput. Sci. 904, 66\u201380 (2022). https:\/\/doi.org\/10.1016\/j.tcs.2021.11.028","DOI":"10.1016\/j.tcs.2021.11.028"},{"issue":"9","key":"10205_CR12","doi-asserted-by":"publisher","first-page":"2586","DOI":"10.1007\/s00453-020-00700-y","volume":"82","author":"R Belmonte","year":"2020","unstructured":"Belmonte, R., Hanaka, T., Lampis, M., Ono, H., Otachi, Y.: Independent set reconfiguration parameterized by modular-width. Algorithmica 82(9), 2586\u20132605 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00700-y","journal-title":"Algorithmica"},{"key":"10205_CR13","doi-asserted-by":"publisher","unstructured":"Censor-Hillel, K., Rabie, M.: Distributed reconfiguration of maximal independent sets. J. Comput. Syst. Sci. 112, 85\u201396 (2020). https:\/\/doi.org\/10.1016\/j.jcss.2020.03.003","DOI":"10.1016\/j.jcss.2020.03.003"},{"key":"10205_CR14","doi-asserted-by":"publisher","unstructured":"Berg, M., Jansen, B.M.P., Mukherjee, D.: Independent-set reconfiguration thresholds of hereditary graph classes. Discret. Appl. Math. 250, 165\u2013182 (2018). https:\/\/doi.org\/10.1016\/j.dam.2018.05.029","DOI":"10.1016\/j.dam.2018.05.029"},{"issue":"1","key":"10205_CR15","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/3280825","volume":"15","author":"D Lokshtanov","year":"2019","unstructured":"Lokshtanov, D., Mouawad, A.E.: The complexity of independent set reconfiguration on bipartite graphs. ACM T. Algorithms 15(1), 7\u20131719 (2019). https:\/\/doi.org\/10.1145\/3280825","journal-title":"ACM T. Algorithms"},{"issue":"1","key":"10205_CR16","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). https:\/\/doi.org\/10.1016\/0166-218X(84)90081-7","journal-title":"Discret. Appl. Math."},{"key":"10205_CR17","doi-asserted-by":"publisher","unstructured":"D\u00f6cker, J., Dorn, B., Linz, S., Semple, C.: Placing quantified variants of 3-SAT and Not-All-Equal 3-SAT in the polynomial hierarchy. Theor. Comput. Sci. 822, 72\u201391 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2020.04.003","DOI":"10.1016\/j.tcs.2020.04.003"},{"issue":"4","key":"10205_CR18","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Tarjan, R.E.: The planar Hamiltonian circuit problem is NP-complete. SIAM J. Comput. 5(4), 704\u2013714 (1976). https:\/\/doi.org\/10.1137\/0205049","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10205_CR19","doi-asserted-by":"publisher","first-page":"543","DOI":"10.7155\/jgaa.00273","volume":"16","author":"D Eppstein","year":"2012","unstructured":"Eppstein, D., Spiro, E.S.: The h-index of a graph and its application to dynamic subgraph statistics. J. Graph Algorithms Appl. 16(2), 543\u2013567 (2012). https:\/\/doi.org\/10.7155\/jgaa.00273","journal-title":"J. Graph Algorithms Appl."},{"key":"10205_CR20","doi-asserted-by":"publisher","unstructured":"Kawarabayashi, K., Kobayashi, Y., Reed, B.A.: The disjoint paths problem in quadratic time. J. Comb. Theory, Ser. B 102(2), 424\u2013435 (2012). https:\/\/doi.org\/10.1016\/j.jctb.2011.07.004","DOI":"10.1016\/j.jctb.2011.07.004"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10205-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10205-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10205-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T17:13:35Z","timestamp":1744132415000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10205-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,23]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["10205"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10205-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2025,1,23]]},"assertion":[{"value":"18 November 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 January 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"7"}}