2026-09-08T01:22:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26497 2026-09-05T19:45:23Z ddc:004 open_access

On (In)approximability of MaxMin Independent Set Reconfiguration Hoang, Hung P. Ohsaka, Naoto Saito, Rin Tamura, Yuma Combinatorial reconfiguration independent set approximation algorithms In the Independent Set Reconfiguration problem under the Token Addition/Removal rule, given a graph G and two independent sets I and J of G, we want to transform I into J by adding and removing vertices, such that all the sets throughout the process are independent sets. Its approximate version called MaxMin Independent Set Reconfiguration aims to maximise the minimum size of the independent sets in the process above. We study the (in)approximability of this problem for general graphs as well as restricted graph classes. Firstly, on general graphs, we obtain a polynomial-time (n / log n)-factor approximation algorithm, complementing the PSPACE-hardness of n^Ω(1)-factor approximation due to Hirahara and Ohsaka [STOC 2024, ICALP 2024] and the NP-hardness of n^{1-ε}-factor approximation due to Ito, Demaine, Harvey, Papadimitriou, Sideri, Uehara, and Uno [TCS 2011]. Secondly, we present a polynomial-time approximation algorithm for degenerate graphs as well as FPT-approximation schemes for bounded-treewidth graphs and H-minor-free graphs. Lastly, we extend the above inapproximability results to bounded-degree graphs, graphs of bandwidth n^{1/2+Θ(1)}, and bipartite graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hung P. Hoang and Naoto Ohsaka and Rin Saito and Yuma Tamura 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.108 urn:nbn:de:0030-drops-264974 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.108 eng https://creativecommons.org/licenses/by/4.0/legalcode