Image de couverture de livre

Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Hirahara, Shuichi, Ohsaka, Naoto, Suga, Tatsuhiro, Suzuki, Akira, Tamura, Yuma, Zhou, Xiao
Format:	Preprint
Publié:	2025
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Optimal PSPACE-hardness of Approximating Set Cover Reconfiguration
par: Hirahara, Shuichi, et autres
Publié: (2024)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
par: Hirahara, Shuichi, et autres
Publié: (2023)

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration
par: Hirahara, Shuichi, et autres
Publié: (2025)

Asymptotically Optimal Inapproximability of Maxmin $k$-Cut Reconfiguration
par: Hirahara, Shuichi, et autres
Publié: (2024)

Changing Induced Subgraph Isomorphisms Under Extended Reconfiguration Rules
par: Suga, Tatsuhiro, et autres
Publié: (2025)

On Approximate Reconfigurability of Label Cover
par: Ohsaka, Naoto
Publié: (2023)

Tight Inapproximability of Target Set Reconfiguration
par: Ohsaka, Naoto
Publié: (2024)

Gap Amplification for Reconfiguration Problems
par: Ohsaka, Naoto
Publié: (2023)

Gap Preserving Reductions Between Reconfiguration Problems
par: Ohsaka, Naoto
Publié: (2022)

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
par: Saito, Rin, et autres
Publié: (2025)

Alphabet Reduction for Reconfiguration Problems
par: Ohsaka, Naoto
Publié: (2024)

On (In)approximability of MaxMin Independent Set Reconfiguration
par: Hoang, Hung P., et autres
Publié: (2026)

Communication Complexity is NP-hard
par: Hirahara, Shuichi, et autres
Publié: (2025)

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
par: Hirahara, Shuichi, et autres
Publié: (2024)

Knapsack with Vertex Cover, Set Cover, and Hitting Set
par: Dey, Palash, et autres
Publié: (2024)

Finding Shortest Reconfiguration Sequences on Independent Set Polytopes
par: Cardinal, Jean, et autres
Publié: (2026)

Coloring Reconfiguration under Color Swapping
par: Fuchs, Janosch, et autres
Publié: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
par: Herrmann, Anton, et autres
Publié: (2025)

Metric Dimension and Geodetic Set Parameterized by Vertex Cover
par: Foucaud, Florent, et autres
Publié: (2024)

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set
par: Chu, Huairui, et autres
Publié: (2023)

One-way Communication Complexity of Minimum Vertex Cover in General Graphs
par: Derakhshan, Mahsa, et autres
Publié: (2025)

Parameterized Capacitated Vertex Cover Revisited
par: Lampis, Michael, et autres
Publié: (2026)

Spanning Trees with a Small Vertex Cover: the Complexity on Specific Graph Classes
par: Kokai, Toranosuke, et autres
Publié: (2025)

Parameterized Max Min Feedback Vertex Set
par: Lampis, Michael, et autres
Publié: (2023)

Exact Algorithms for Distance to Unique Vertex Cover
par: Fioravantes, Foivos, et autres
Publié: (2025)

Geodetic Set on Graphs of Constant Pathwidth and Feedback Vertex Set Number
par: Tale, Prafullkumar
Publié: (2025)

Temporal Reachability Dominating Sets: contagion in temporal graphs
par: Kutner, David C., et autres
Publié: (2023)

Hardness of SetCover Reoptimization
par: Jansen, Klaus, et autres
Publié: (2025)

Special Coverings of Sets and Boolean Functions
par: Margaryan, Stepan
Publié: (2024)

Recognizing and Realizing Temporal Reachability Graphs
par: Erlebach, Thomas, et autres
Publié: (2025)

A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
par: Clinch, Katie, et autres
Publié: (2025)

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

On the Complexity of Claw-Free Vertex Splitting
par: Abu-Khzam, Faisal N., et autres
Publié: (2025)

On the Complexity of Vertex-Splitting Into an Interval Graph
par: Abu-Khzam, Faisal N., et autres
Publié: (2026)

Rounding Large Independent Sets on Expanders
par: Bafna, Mitali, et autres
Publié: (2024)

The Parameterized Complexity of Computing the Linear Vertex Arboricity
par: Erhardt, Alexander, et autres
Publié: (2025)

Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs
par: Casteigts, Arnaud, et autres
Publié: (2024)

Deterministic Independent Sets in the Semi-Streaming Model
par: Ye, Daniel
Publié: (2025)

Fermionic Independent Set and Laplacian of an independence complex are QMA-hard
par: Rayudu, Chaithanya
Publié: (2024)

Reachability In Simple Neural Networks
par: Sälzer, Marco, et autres
Publié: (2022)