pith. machine review for the scientific record. sign in

arxiv: 2604.26714 · v1 · submitted 2026-04-29 · 💻 cs.DS

Recognition: unknown

On (In)approximability of MaxMin Independent Set Reconfiguration

Hung P. Hoang , Naoto Ohsaka , Rin Saito , Yuma Tamura
Authors on Pith no claims yet

Pith reviewed 2026-05-07 10:51 UTC · model grok-4.3

classification 💻 cs.DS
keywords independent set reconfigurationtoken addition removalapproximation algorithmsinapproximabilitydegenerate graphsbounded treewidthH-minor-free graphsbipartite graphs
0
0 comments X

The pith

A polynomial-time n/log n-factor approximation algorithm exists for MaxMin Independent Set Reconfiguration on general graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the MaxMin Independent Set Reconfiguration problem under the token addition and removal rule, where the goal is to transform one independent set into another while maximizing the size of the smallest independent set appearing in the sequence. For general graphs the authors give a polynomial-time algorithm that guarantees a solution within a factor of n over log n of the optimum. They also supply a polynomial-time approximation for degenerate graphs together with fixed-parameter tractable approximation schemes on bounded-treewidth graphs and H-minor-free graphs. In addition the paper carries over the known strong inapproximability lower bounds to the classes of bounded-degree graphs, graphs whose bandwidth is roughly the square root of n, and bipartite graphs.

Core claim

On general graphs a polynomial-time (n / log n)-factor approximation algorithm is obtained for MaxMin Independent Set Reconfiguration. This complements the PSPACE-hardness of n to the Omega(1) approximation shown by Hirahara and Ohsaka and the NP-hardness of n to the 1-epsilon approximation shown by Ito et al. Polynomial-time approximation algorithms are presented for degenerate graphs, and FPT-approximation schemes are given for bounded-treewidth graphs and H-minor-free graphs. The inapproximability results are extended to bounded-degree graphs, graphs of bandwidth n to the power 1/2 plus Theta(1), and bipartite graphs.

What carries the argument

The MaxMin objective under token addition/removal reconfiguration, which requires every intermediate set in the sequence to remain independent while maximizing the size of the smallest set that appears.

If this is right

  • A reconfiguration sequence whose bottleneck independent set is at least OPT divided by n over log n can be found in polynomial time on any graph.
  • On degenerate graphs a polynomial-time approximation whose ratio depends only on the degeneracy parameter is available.
  • On bounded-treewidth graphs an approximation scheme whose running time is FPT in the treewidth parameter exists.
  • The same strong hardness of approximation that holds on general graphs continues to hold even when the input is restricted to bounded-degree graphs or bipartite graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The n over log n ratio suggests that the problem sits in an intermediate regime between fully approximable and fully inapproximable reconfiguration tasks.
  • The extension of hardness to low-bandwidth graphs indicates that the problem remains difficult even on instances that admit efficient dynamic programming on path-like decompositions.
  • The FPT schemes on minor-free graphs may be adaptable to other sparse graph classes that exclude a fixed minor.

Load-bearing premise

The inapproximability extensions rest on the correctness of reductions from earlier PSPACE-hardness and NP-hardness results for related reconfiguration problems.

What would settle it

An explicit family of graphs on which every valid reconfiguration sequence has minimum independent-set size smaller than OPT times log n over n would falsify the approximation guarantee.

read the original abstract

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 $\mathsf{PSPACE}$-hardness of $n^{\Omega(1)}$-factor approximation due to Hirahara and Ohsaka [STOC 2024, ICALP 2024] and the $\mathsf{NP}$-hardness of $n^{1-\varepsilon}$-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 $\mathsf{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^{\frac{1}{2}+\Theta(1)}$, and bipartite graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript studies the MaxMin Independent Set Reconfiguration problem (maximizing the minimum independent-set size over token-addition/removal sequences from I to J). It claims a polynomial-time (n/log n)-approximation for general graphs (complementing PSPACE-hardness of n^Ω(1)-approximation and NP-hardness of n^{1-ε}-approximation), a polynomial-time approximation algorithm for degenerate graphs, FPT-approximation schemes for bounded-treewidth and H-minor-free graphs, and extensions of the cited hardness results to bounded-degree graphs, bandwidth-n^{1/2+Θ(1)} graphs, and bipartite graphs.

Significance. If the algorithmic constructions and reduction fidelity hold, the paper advances the approximability landscape for reconfiguration problems by supplying both positive results on restricted classes and broadened hardness statements. The (n/log n) approximation and FPT schemes for structured graphs are concrete contributions that could be useful in practice; the hardness extensions, if gap-preserving, strengthen the applicability of prior STOC/ICALP and TCS results.

major comments (1)
  1. [Inapproximability extensions] Inapproximability extensions (the section presenting the reductions from Hirahara-Ohsaka and Ito et al.): the claim that PSPACE-hardness of n^Ω(1)-approximation and NP-hardness of n^{1-ε}-approximation carry over to bounded-degree, bandwidth-n^{1/2+Θ(1)}, and bipartite graphs requires explicit verification that each reduction preserves the gap between the MaxMin value and the target approximation threshold. In particular, the construction must be shown not to introduce reconfiguration shortcuts that increase the minimum independent-set size along valid sequences; without the full reduction description and gap analysis, the inherited hardness factors cannot be confirmed.
minor comments (1)
  1. [Abstract] The abstract states a 'polynomial-time approximation algorithm for degenerate graphs' without naming the approximation ratio; this detail should appear in the abstract or introduction for clarity.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the thorough review and constructive feedback on our manuscript. We address the major comment regarding the inapproximability extensions below.

read point-by-point responses

  1. Referee: [Inapproximability extensions] Inapproximability extensions (the section presenting the reductions from Hirahara-Ohsaka and Ito et al.): the claim that PSPACE-hardness of n^Ω(1)-approximation and NP-hardness of n^{1-ε}-approximation carry over to bounded-degree, bandwidth-n^{1/2+Θ(1)}, and bipartite graphs requires explicit verification that each reduction preserves the gap between the MaxMin value and the target approximation threshold. In particular, the construction must be shown not to introduce reconfiguration shortcuts that increase the minimum independent-set size along valid sequences; without the full reduction description and gap analysis, the inherited hardness factors cannot be confirmed.

    Authors: We appreciate the referee's request for explicit verification of gap preservation. Our extensions adapt the reductions from Hirahara-Ohsaka and Ito et al. using standard gadget replacements that maintain the original independent-set constraints. For bounded-degree graphs, the gadgets are chosen to be constant-degree and ensure that any reconfiguration sequence must respect the same size lower bounds as in the source instance, with no additional shortcuts possible due to local independence enforcement. For bandwidth-n^{1/2+Θ(1)} graphs, the construction embeds the original instance into a layout with controlled bandwidth (via path-like or grid gadgets) that limits token movements and prevents bypassing the hardness gap. For bipartite graphs, we employ bipartition-respecting gadgets that preserve the reconfiguration dynamics without inflating the minimum independent-set size along sequences. The manuscript contains high-level arguments for these properties, but we agree that a more detailed gap analysis subsection is warranted. We will revise the relevant section to include explicit proofs that valid sequences in the target graphs cannot achieve a strictly larger minimum size than permitted by the original hardness instances, thereby confirming the inherited factors. revision: yes

Circularity Check

0 steps flagged

No significant circularity; new algorithms and reductions are independent of inputs

full rationale

The paper's derivation chain consists of new polynomial-time approximation algorithms (n/log n factor for general graphs, plus results for degenerate, bounded-treewidth, and H-minor-free graphs) and explicit new reductions extending prior hardness results to bounded-degree, bandwidth, and bipartite graphs. These steps rely on standard algorithmic techniques and gap-preserving reductions rather than any self-definitional equivalence, fitted parameters renamed as predictions, or load-bearing self-citations that collapse to unverified inputs. The cited base hardness results (Hirahara-Ohsaka and Ito et al.) are external to the present derivations, and the extensions are constructed and analyzed within this work without reducing the claimed approximability or inapproximability factors to the paper's own assumptions by construction. No quoted equations or steps exhibit the enumerated circular patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard graph-theoretic definitions and complexity assumptions without introducing new free parameters or invented entities.

axioms (2)
  • domain assumption Standard assumptions in complexity theory such as P ≠ NP for NP-hardness statements.
    Invoked implicitly for the NP-hardness and inapproximability results.
  • standard math Basic graph theory: independent sets, degeneracy, treewidth, and minor-closed families.
    Foundational definitions used throughout the problem statement and results.

pith-pipeline@v0.9.0 · 5582 in / 1371 out tokens · 61921 ms · 2026-05-07T10:51:42.004717+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

53 extracted references · 52 canonical work pages

  1. [1]

    Akanksha Agrawal, Soumita Hait, and Amer E. Mouawad. On finding short reconfiguration sequences between independent sets. Journal of Computer and System Sciences , 147:103578, 2025. https://doi.org/10.1016/J.JCSS.2024.103578 doi:10.1016/J.JCSS.2024.103578

    work page doi:10.1016/j.jcss.2024.103578 2025

  2. [2]

    Proof verification and the hardness of approximation problems

    Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM , 45(3):501--555, 1998. https://doi.org/10.1145/278298.278306 doi:10.1145/278298.278306

    work page doi:10.1145/278298.278306 1998

  3. [3]

    Probabilistic checking of proofs: A new characterization of NP

    Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP . Journal of the ACM , 45(1):70--122, 1998. https://doi.org/10.1145/273865.273901 doi:10.1145/273865.273901

    work page doi:10.1145/273865.273901 1998

  4. [4]

    Inapproximability of vertex cover and independent set in bounded degree graphs

    Per Austrin, Subhash Khot, and Muli Safra. Inapproximability of vertex cover and independent set in bounded degree graphs. Theory of Computing , 7(3):27--43, 2011. https://doi.org/10.4086/toc.2011.v007a003 doi:10.4086/toc.2011.v007a003

    work page doi:10.4086/toc.2011.v007a003 2011

  5. [5]

    Brenda S. Baker. Approximation algorithms for NP -complete problems on planar graphs. Journal of the ACM , 41(1):153--180, 1994. https://doi.org/10.1145/174644.174650 doi:10.1145/174644.174650

    work page doi:10.1145/174644.174650 1994

  6. [6]

    UG -hardness to NP -hardness by losing half

    Amey Bhangale and Subhash Khot. UG -hardness to NP -hardness by losing half. Theory of Computing , 18(5):1--28, 2022. https://doi.org/10.4086/toc.2022.v018a005 doi:10.4086/toc.2022.v018a005

    work page doi:10.4086/toc.2022.v018a005 2022

  7. [7]

    Bodlaender , title =

    Hans L. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing , 25(6):1305--1317, 1996. https://doi.org/10.1137/S0097539793251219 doi:10.1137/S0097539793251219

    work page doi:10.1137/s0097539793251219 1996

  8. [8]

    Bodlaender, Carla Groenland, and C \' e line M

    Hans L. Bodlaender, Carla Groenland, and C \' e line M. F. Swennenhuis. Parameterized complexities of dominating and independent set reconfiguration. In Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC) , pages 9:1--9:16, 2021. https://doi.org/10.4230/LIPICS.IPEC.2021.9 doi:10.4230/LIPICS.IPEC.2021.9

    work page doi:10.4230/lipics.ipec.2021.9 2021

  9. [9]

    Token jumping in minor-closed classes

    Nicolas Bousquet, Arnaud Mary, and Aline Parreau. Token jumping in minor-closed classes. In Proceedings of the International Symposium on Fundamentals of Computation Theory (FCT) , pages 136--149, 2017. https://doi.org/10.1007/978-3-662-55751-8\_12 doi:10.1007/978-3-662-55751-8\_12

    work page doi:10.1007/978-3-662-55751-8 2017

  10. [10]

    Mouawad, Naomi Nishimura, and Sebastian Siebertz

    Nicolas Bousquet, Amer E. Mouawad, Naomi Nishimura, and Sebastian Siebertz. A survey on the parameterized complexity of reconfiguration problems. Computer Science Review , 53:100663, 2024. https://doi.org/10.1016/j.cosrev.2024.100663 doi:10.1016/j.cosrev.2024.100663

    work page doi:10.1016/j.cosrev.2024.100663 2024

  11. [11]

    Michael B. Cohen. Ramanujan graphs in polynomial time. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) , pages 276--281, 2016. https://doi.org/10.1109/FOCS.2016.37 doi:10.1109/FOCS.2016.37

    work page doi:10.1109/focs.2016.37 2016

  12. [12]

    Fomin and Lukasz Kowalik and Daniel Lokshtanov and D

    Marek Cygan, Fedor V. Fomin, ukasz Kowalik, Daniel Lokshtanov, D \'a niel Marx, Marcin Pilipczuk, Micha Pilipczuk, and Saket Saurabh. Parameterized Algorithms . Springer, 2015. https://doi.org/10.1007/978-3-319-21275-3 doi:10.1007/978-3-319-21275-3

    work page doi:10.1007/978-3-319-21275-3 2015

  13. [13]

    Demaine, MohammadTaghi Hajiaghayi, and Ken ichi Kawarabayashi

    Erik D. Demaine, Mohammad Taghi Hajiaghayi, and Ken - ichi Kawarabayashi. Algorithmic graph minor theory: Decomposition, approximation, and coloring. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) , pages 637--646, 2005. https://doi.org/10.1109/SFCS.2005.14 doi:10.1109/SFCS.2005.14

    work page doi:10.1109/sfcs.2005.14 2005

  14. [14]

    Fundamentals of Parameterized Complexity

    Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity . Texts in Computer Science. Springer, London, 2013. https://doi.org/10.1007/978-1-4471-5559-1 doi:10.1007/978-1-4471-5559-1

    work page doi:10.1007/978-1-4471-5559-1 2013

  15. [15]

    Approximating maximum clique by removing subgraphs

    Uriel Feige. Approximating maximum clique by removing subgraphs. SIAM Journal on Discrete Mathematics , 18(2):219--225, 2004. https://doi.org/10.1137/S089548010240415X doi:10.1137/S089548010240415X

    work page doi:10.1137/s089548010240415x 2004

  16. [16]

    Andreas Emil Feldmann, Karthik C. S. , Euiwoong Lee, and Pasin Manurangsi. A survey on approximation in parameterized complexity: Hardness and algorithms. Algorithms , 13(6):146, 2020. https://doi.org/10.3390/a13060146 doi:10.3390/a13060146

    work page doi:10.3390/a13060146 2020

  17. [17]

    Venkatesan Guruswami, Karthik C. S. , Pasin Manurangsi, Xuandi Ren, and Kewen Wu. On inapproximability of reconfiguration problems: PSPACE -hardness and some tight NP -hardness results. Computing Research Repository , abs/2312.17140v3, 2025. URL: https://arxiv.org/abs/2312.17140v3, https://arxiv.org/abs/2312.17140v3 arXiv:2312.17140v3

    work page arXiv 2025

  18. [18]

    Eigenvalue techniques in design and graph theory

    Wilhelmus Hubertus Haemers. Eigenvalue techniques in design and graph theory . PhD thesis, Mathematisch Centrum, Amsterdam, 1979. https://doi.org/10.6100/IR41103 doi:10.6100/IR41103

    work page doi:10.6100/ir41103 1979

  19. [19]

    Interlacing eigenvalues and graphs

    Wilhelmus Hubertus Haemers. Interlacing eigenvalues and graphs. Linear Algebra and its Applications , 226--228:593--616, 1995. https://doi.org/10.1016/0024-3795(95)00199-2 doi:10.1016/0024-3795(95)00199-2

    work page doi:10.1016/0024-3795(95)00199-2 1995

  20. [20]

    Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs

    Eran Halperin. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. SIAM Journal on Computing , 31(5):1608--1623, 2002. https://doi.org/10.1137/S0097539700381097 doi:10.1137/S0097539700381097

    work page doi:10.1137/s0097539700381097 2002

  21. [21]

    Clique is hard to approximate withinn 1−ε.Acta Mathematica, 182(1), 1999

    Johan H stad. Clique is hard to approximate within n^ 1- . Acta Mathematica , 182(1):105--142, 1999. https://doi.org/10.1007/BF02392825 doi:10.1007/BF02392825

    work page doi:10.1007/bf02392825 1999

  22. [22]

    Hearn and Erik D

    Robert A. Hearn and Erik D. Demaine. PSPACE -completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science , 343(1-2):72--96, 2005. https://doi.org/10.1016/j.tcs.2005.05.008 doi:10.1016/j.tcs.2005.05.008

    work page doi:10.1016/j.tcs.2005.05.008 2005

  23. [23]

    Hearn and Erik D

    Robert A. Hearn and Erik D. Demaine. Games, Puzzles, and Computation . A K Peters, Ltd., 2009

    2009

  24. [24]

    Heath and John Paul C

    Lenwood S. Heath and John Paul C. Vergara. Sorting by short swaps. Journal of Computational Biology , 10(5):775--789, 2003. https://doi.org/10.1089/106652703322539097 doi:10.1089/106652703322539097

    work page doi:10.1089/106652703322539097 2003

  25. [25]

    Optimal PSPACE -hardness of approximating set cover reconfiguration

    Shuichi Hirahara and Naoto Ohsaka. Optimal PSPACE -hardness of approximating set cover reconfiguration. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) , pages 85:1--85:18, 2024. https://doi.org/10.4230/LIPIcs.ICALP.2024.85 doi:10.4230/LIPIcs.ICALP.2024.85

    work page doi:10.4230/lipics.icalp.2024.85 2024

  26. [26]

    Probabilistically checkable reconfiguration proofs and inapproximability of reconfiguration problems

    Shuichi Hirahara and Naoto Ohsaka. Probabilistically checkable reconfiguration proofs and inapproximability of reconfiguration problems. In Proceedings of the ACM Symposium on Theory of Computing (STOC) , pages 1435--1445, 2024. https://doi.org/10.1145/3618260.3649667 doi:10.1145/3618260.3649667

    work page doi:10.1145/3618260.3649667 2024

  27. [27]

    Asymptotically optimal inapproximability of E k -SAT reconfiguration

    Shuichi Hirahara and Naoto Ohsaka. Asymptotically optimal inapproximability of E k -SAT reconfiguration. In Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS) , pages 858--869, 2025. https://doi.org/10.1109/FOCS63196.2025.00018 doi:10.1109/FOCS63196.2025.00018

    work page doi:10.1109/focs63196.2025.00018 2025

  28. [28]

    Asymptotically optimal inapproximability of maxmin k -cut reconfiguration

    Shuichi Hirahara and Naoto Ohsaka. Asymptotically optimal inapproximability of maxmin k -cut reconfiguration. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) , pages 96:1--96:18, 2025. https://doi.org/10.4230/LIPIcs.ICALP.2025.96 doi:10.4230/LIPIcs.ICALP.2025.96

    work page doi:10.4230/lipics.icalp.2025.96 2025

  29. [29]

    Expander graphs and their applications

    Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society , 43(4):439--561, 2006. https://doi.org/10.1090/S0273-0979-06-01126-8 doi:10.1090/S0273-0979-06-01126-8

    work page doi:10.1090/s0273-0979-06-01126-8 2006

  30. [30]

    Takehiro Ito and Erik D. Demaine. Approximability of the subset sum reconfiguration problem. Journal of Combinatorial Optimization , 28(3):639--654, 2014. https://doi.org/10.1007/s10878-012-9562-z doi:10.1007/s10878-012-9562-z

    work page doi:10.1007/s10878-012-9562-z 2014

  31. [31]

    Demaine and Nicholas J.A

    Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno. On the complexity of reconfiguration problems. Theoretical Computer Science , 412(12-14):1054--1065, 2011. https://doi.org/10.1016/j.tcs.2010.12.005 doi:10.1016/j.tcs.2010.12.005

    work page doi:10.1016/j.tcs.2010.12.005 2011

  32. [32]

    Parameterized complexity of independent set reconfiguration problems

    Takehiro Ito, Marcin Jakub Kami\' n ski, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, and Katsuhisa Yamanaka. Parameterized complexity of independent set reconfiguration problems. Discrete Applied Mathematics , 283:336--345, 2020. https://doi.org/10.1016/J.DAM.2020.01.022 doi:10.1016/J.DAM.2020.01.022

    work page doi:10.1016/j.dam.2020.01.022 2020

  33. [33]

    Complexity of independent set reconfigurability problems

    Marcin Kami\' n ski, Paul Medvedev, and Martin Milani c . Complexity of independent set reconfigurability problems. Theoretical Computer Science , 439:9--15, 2012. https://doi.org/10.1016/j.tcs.2012.03.004 doi:10.1016/j.tcs.2012.03.004

    work page doi:10.1016/j.tcs.2012.03.004 2012

  34. [34]

    Daniel Lokshtanov and Amer E. Mouawad. The complexity of independent set reconfiguration on bipartite graphs. ACM Transactions on Algorithms , 15(1):7:1--7:19, 2019. https://doi.org/10.1145/3280825 doi:10.1145/3280825

    work page doi:10.1145/3280825 2019

  35. [35]

    Ramanujan graphs

    Alexander Lubotzky, Ralph Phillips, and Peter Sarnak. Ramanujan graphs. Combinatorica , 8(3):261--277, 1988. https://doi.org/10.1007/BF02126799 doi:10.1007/BF02126799

    work page doi:10.1007/bf02126799 1988

  36. [36]

    Inapproximability of maximum biclique problems, minimum k-cut and densest at-least-k-subgraph from the small set expansion hypothesis

    Pasin Manurangsi. Inapproximability of maximum biclique problems, minimum k-cut and densest at-least-k-subgraph from the small set expansion hypothesis. Algorithms , 11(1):10, 2018. https://doi.org/10.3390/A11010010 doi:10.3390/A11010010

    work page doi:10.3390/a11010010 2018

  37. [37]

    Marcus, Daniel A

    Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava. Interlacing families I : Bipartite Ramanujan graphs of all degrees. Annals of Mathematics , 182:307--325, 2015. https://doi.org/10.4007/annals.2015.182.1.7 doi:10.4007/annals.2015.182.1.7

    work page doi:10.4007/annals.2015.182.1.7 2015

  38. [38]

    Marcus, Daniel A

    Adam W. Marcus, Daniel A. Spielman, and Nikhil Srivastava. Interlacing families IV : Bipartite Ramanujan graphs of all sizes. SIAM Journal on Computing , 47(6):2488--2509, 2018. https://doi.org/10.1137/16M106176X doi:10.1137/16M106176X

    work page doi:10.1137/16m106176x 2018

  39. [39]

    Parameterized complexity and approximation algorithms

    D \'a niel Marx. Parameterized complexity and approximation algorithms. The Computer Journal , 51(1):60--78, 2008. https://doi.org/10.1093/comjnl/bxm048 doi:10.1093/comjnl/bxm048

    work page doi:10.1093/comjnl/bxm048 2008

  40. [40]

    Approximation and hardness of token swapping

    Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, G\" u nter Rote, Antonis Thomas, and Takeaki Uno. Approximation and hardness of token swapping. In Proceedings of the European Symposium on Algorithms (ESA) , pages 66:1--66:15, 2016. https://doi.org/10.4230/LIPIcs.ESA.2016.66 doi:10.4230/LIPIcs.ESA.2016.66

    work page doi:10.4230/lipics.esa.2016.66 2016

  41. [41]

    Mouawad, Naomi Nishimura, Venkatesh Raman, Narges Simjour, and Akira Suzuki

    Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Narges Simjour, and Akira Suzuki. On the parameterized complexity of reconfiguration problems. Algorithmica , 78(1):274--297, 2017. https://doi.org/10.1007/S00453-016-0159-2 doi:10.1007/S00453-016-0159-2

    work page doi:10.1007/s00453-016-0159-2 2017

  42. [42]

    Gap preserving reductions between reconfiguration problems

    Naoto Ohsaka. Gap preserving reductions between reconfiguration problems. In Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS) , pages 49:1--49:18, 2023. https://doi.org/10.4230/LIPIcs.STACS.2023.49 doi:10.4230/LIPIcs.STACS.2023.49

    work page doi:10.4230/lipics.stacs.2023.49 2023

  43. [43]

    Alphabet reduction for reconfiguration problems

    Naoto Ohsaka. Alphabet reduction for reconfiguration problems. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) , pages 113:1--113:17, 2024. https://doi.org/10.4230/LIPIcs.ICALP.2024.113 doi:10.4230/LIPIcs.ICALP.2024.113

    work page doi:10.4230/lipics.icalp.2024.113 2024

  44. [44]

    Gap amplification for reconfiguration problems

    Naoto Ohsaka. Gap amplification for reconfiguration problems. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1345--1366, 2024. https://doi.org/10.1137/1.9781611977912.54 doi:10.1137/1.9781611977912.54

    work page doi:10.1137/1.9781611977912.54 2024

  45. [45]

    On approximate reconfigurability of label cover

    Naoto Ohsaka. On approximate reconfigurability of label cover. Information Processing Letters , 189:106556, 2025. https://doi.org/10.1016/j.ipl.2024.106556 doi:10.1016/j.ipl.2024.106556

    work page doi:10.1016/j.ipl.2024.106556 2025

  46. [46]

    Yet another simple proof of the PCRP theorem

    Naoto Ohsaka. Yet another simple proof of the PCRP theorem. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP) , pages 122:1--122:18, 2025. https://doi.org/10.4230/LIPIcs.ICALP.2025.122 doi:10.4230/LIPIcs.ICALP.2025.122

    work page doi:10.4230/lipics.icalp.2025.122 2025

  47. [47]

    Reconfiguration problems on submodular functions

    Naoto Ohsaka and Tatsuya Matsuoka. Reconfiguration problems on submodular functions. In Proceedings of the ACM International Conference on Web Search and Data Mining (WSDM) , pages 764--774, 2022. https://doi.org/10.1145/3488560.3498382 doi:10.1145/3488560.3498382

    work page doi:10.1145/3488560.3498382 2022

  48. [48]

    Graph expansion and the unique games conjecture

    Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In Proceedings of the ACM Symposium on Theory of Computing (STOC) , pages 755--764, 2010. https://doi.org/10.1145/1806689.1806792 doi:10.1145/1806689.1806792

    work page doi:10.1145/1806689.1806792 2010

  49. [49]

    The extremal function for complete minors

    Andrew Thomason. The extremal function for complete minors. Journal of Combinatorial Theory, Series B , 81(2):318--338, 2001. https://doi.org/10.1006/jctb.2000.2013 doi:10.1006/jctb.2000.2013

    work page doi:10.1006/jctb.2000.2013 2001

  50. [50]

    van der Zanden

    Tom C. van der Zanden. Parameterized complexity of graph constraint logic. In Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC) , pages 282--293. 2015. https://doi.org/10.4230/LIPIcs.IPEC.2015.282 doi:10.4230/LIPIcs.IPEC.2015.282

    work page doi:10.4230/lipics.ipec.2015.282 2015

  51. [51]

    Reconfiguration in bounded bandwidth and tree-depth

    Marcin Wrochna. Reconfiguration in bounded bandwidth and tree-depth. Journal of Computer and System Sciences , 93:1--10, 2018. https://doi.org/10.1016/j.jcss.2017.11.003 doi:10.1016/j.jcss.2017.11.003

    work page doi:10.1016/j.jcss.2017.11.003 2018

  52. [52]

    Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno

    Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno. Swapping labeled tokens on graphs. Theoretical Computer Science , 586:81--94, 2015. https://doi.org/10.1016/j.tcs.2015.01.052 doi:10.1016/j.tcs.2015.01.052

    work page doi:10.1016/j.tcs.2015.01.052 2015

  53. [53]

    Theory Comput

    David Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. Theory of Computing , 3:103--128, 2007. https://doi.org/10.4086/toc.2007.v003a006 doi:10.4086/toc.2007.v003a006

    work page doi:10.4086/toc.2007.v003a006 2007