:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Hirahara, Shuichi, Ohsaka, Naoto, Suga, Tatsuhiro, Suzuki, Akira, Tamura, Yuma, Zhou, Xiao
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2510.24226
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2024)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
by: Hirahara, Shuichi, et al.
Published: (2023)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2025)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
by: Hirahara, Shuichi, et al.
Published: (2024)

Changing Induced Subgraph Isomorphisms Under Extended Reconfiguration Rules
by: Suga, Tatsuhiro, et al.
Published: (2025)

On Approximate Reconfigurability of Label Cover
by: Ohsaka, Naoto
Published: (2023)

Tight Inapproximability of Target Set Reconfiguration
by: Ohsaka, Naoto
Published: (2024)

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
by: Saito, Rin, et al.
Published: (2025)

Gap Amplification for Reconfiguration Problems
by: Ohsaka, Naoto
Published: (2023)

Gap Preserving Reductions Between Reconfiguration Problems
by: Ohsaka, Naoto
Published: (2022)

Alphabet Reduction for Reconfiguration Problems
by: Ohsaka, Naoto
Published: (2024)

On (In)approximability of MaxMin Independent Set Reconfiguration
by: Hoang, Hung P., et al.
Published: (2026)

Communication Complexity is NP-hard
by: Hirahara, Shuichi, et al.
Published: (2025)

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
by: Hirahara, Shuichi, et al.
Published: (2024)

Knapsack with Vertex Cover, Set Cover, and Hitting Set
by: Dey, Palash, et al.
Published: (2024)

Coloring Reconfiguration under Color Swapping
by: Fuchs, Janosch, et al.
Published: (2025)

Finding Shortest Reconfiguration Sequences on Independent Set Polytopes
by: Cardinal, Jean, et al.
Published: (2026)

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
by: Foucaud, Florent, et al.
Published: (2024)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
by: Herrmann, Anton, et al.
Published: (2025)

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
by: Chu, Huairui, et al.
Published: (2023)

Spanning Trees with a Small Vertex Cover: the Complexity on Specific Graph Classes
by: Kokai, Toranosuke, et al.
Published: (2025)

Parameterized Capacitated Vertex Cover Revisited
by: Lampis, Michael, et al.
Published: (2026)

One-way Communication Complexity of Minimum Vertex Cover in General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)

Parameterized Max Min Feedback Vertex Set
by: Lampis, Michael, et al.
Published: (2023)

Exact Algorithms for Distance to Unique Vertex Cover
by: Fioravantes, Foivos, et al.
Published: (2025)

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
by: Tale, Prafullkumar
Published: (2025)

Temporal Reachability Dominating Sets: contagion in temporal graphs
by: Kutner, David C., et al.
Published: (2023)

On the Complexity of Distance-$d$ Independent Set Reconfiguration
by: Hoang, Duc A.
Published: (2022)

Hardness of SetCover Reoptimization
by: Jansen, Klaus, et al.
Published: (2025)

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
by: Clinch, Katie, et al.
Published: (2025)

Special Coverings of Sets and Boolean Functions
by: Margaryan, Stepan
Published: (2024)

Recognizing and Realizing Temporal Reachability Graphs
by: Erlebach, Thomas, et al.
Published: (2025)

Rounding Large Independent Sets on Expanders
by: Bafna, Mitali, et al.
Published: (2024)

On the Complexity of Claw-Free Vertex Splitting
by: Abu-Khzam, Faisal N., et al.
Published: (2025)

On the Complexity of Vertex-Splitting Into an Interval Graph
by: Abu-Khzam, Faisal N., et al.
Published: (2026)

Deterministic Independent Sets in the Semi-Streaming Model
by: Ye, Daniel
Published: (2025)

The Parameterized Complexity of Computing the Linear Vertex Arboricity
by: Erhardt, Alexander, et al.
Published: (2025)

A Linear Kernel for Independent Set Reconfiguration in Planar Graphs
by: Bousquet, Nicolas, et al.
Published: (2025)

Computing Subset Vertex Covers in $H$-Free Graphs
by: Brettell, Nick, et al.
Published: (2023)

Reachability In Simple Neural Networks
by: Sälzer, Marco, et al.
Published: (2022)