:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Silva, Lucas de Oliveira, Chagas, Vítor Gomes, de Paula, Samuel Plaça, Quesquén, Greis Yvet Oropeza, Souza, Uéverton dos Santos
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2502.09358
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A tight quasi-polynomial bound for Global Label Min-Cut
by: Jaffke, Lars, et al.
Published: (2022)

Optimizing for aggressive-style strategies in Flesh and Blood is NP-hard
by: Romão, Leonardo Gasparini, et al.
Published: (2025)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
by: S., Karthik C., et al.
Published: (2023)

Closing the complexity gap of the double distance problem
by: Cunha, Luís, et al.
Published: (2024)

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

Freeze-Tag is NP-hard in 2D with $L_1$ distance
by: Silva, Lucas de Oliveira, et al.
Published: (2025)

Finding d-Cuts in Claw-free Graphs
by: Ahn, Jungho, et al.
Published: (2025)

Finding Minimum Matching Cuts in $H$-free Graphs
by: Lucke, Felicia, et al.
Published: (2025)

Matching Cut and Variants on Bipartite Graphs of Bounded Radius and Diameter
by: Lucke, Felicia
Published: (2025)

Parameterized Local Search for Max $c$-Cut
by: Garvardt, Jaroslav, et al.
Published: (2024)

Realizing Metric Spaces with Convex Obstacles
by: Kisfaludi-Bak, Sándor, et al.
Published: (2025)

Domination in Diameter-Two Graphs and the 2-Club Cluster Vertex Deletion Parameter
by: Abu-Khzam, Faisal N., et al.
Published: (2024)

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

Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
by: de Rezende, Susanna F., et al.
Published: (2024)

Knapsack on Graphs with Relaxed Neighborhood Constraints
by: Dey, Palash, et al.
Published: (2025)

Finding $d$-Cuts in Probe $H$-Free Graphs
by: Dabrowski, Konrad K., et al.
Published: (2025)

Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
by: Lucke, Felicia, et al.
Published: (2024)

Minimum Stable Cut and Treewidth
by: Lampis, Michael
Published: (2021)

Quantum Max-Cut is NP hard to approximate
by: Piddock, Stephen
Published: (2025)

Pseudodeterministic Algorithms for Minimum Cut Problems
by: Agarwala, Aryan, et al.
Published: (2025)

Parameterized Critical Node Cut Revisited
by: Knop, Dušan, et al.
Published: (2025)

Envy-Free Cake-Cutting for Four Agents
by: Hollender, Alexandros, et al.
Published: (2023)

Algebraic Global Gadgetry for Surjective Constraint Satisfaction
by: Chen, Hubie
Published: (2020)

Consistent Query Answering over SHACL Constraints
by: Ahmetaj, Shqiponja, et al.
Published: (2024)

Factorization norms and an inverse theorem for MaxCut
by: Balla, Igor, et al.
Published: (2025)

Game Derandomization
by: Epstein, Samuel
Published: (2024)

On Kolmogorov Structure Functions
by: Epstein, Samuel
Published: (2024)

The Randomness Deficiency Function and the Shift Operator
by: Epstein, Samuel
Published: (2023)

On the Existence of Anomalies, The Reals Case
by: Epstein, Samuel
Published: (2023)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
by: Johnson, Matthew, et al.
Published: (2022)

Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting
by: Gao, Ruiquan, et al.
Published: (2024)

Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
by: Lichter, Moritz, et al.
Published: (2024)

Query Lower Bounds for Correlation Clustering under Memory Constraints
by: Garg, Sumegha, et al.
Published: (2026)

U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
by: Kratochvíl, Jan, et al.
Published: (2020)

The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side
by: Asimi, Kristina, et al.
Published: (2024)

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
by: Michel, Lukas, et al.
Published: (2023)

Maximizing Phylogenetic Diversity under Ecological Constraints: A Parameterized Complexity Study
by: Komusiewicz, Christian, et al.
Published: (2024)

Temporal Cycle Detection and Acyclic Temporization
by: de Andrade, Davi, et al.
Published: (2025)

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
by: Kenig, Batya
Published: (2025)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
by: Adriaens, Florian, et al.
Published: (2024)