Imagen de Portada

Hardness of Hypergraph Edge Modification Problems

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Gishboliner, Lior, Levanzov, Yevgeny, Shapira, Asaf
Formato:	Preprint
Publicado:	2025
Materias:	Combinatorics Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Hypergraph removal with polynomial bounds
por: Gishboliner, Lior, et al.
Publicado: (2022)

Polynomial Property Testing
por: Gishboliner, Lior, et al.
Publicado: (2025)

A Fast Coloring Oracle for Average Case Hypergraphs
por: Marcussen, Cassandra, et al.
Publicado: (2025)

Regularity for hypergraphs with bounded VC$_2$ dimension
por: Gishboliner, Lior, et al.
Publicado: (2025)

Is it easy to regularize a hypergraph with easy links?
por: Gishboliner, Lior, et al.
Publicado: (2025)

An efficient asymmetric removal lemma and its limitations
por: Gishboliner, Lior, et al.
Publicado: (2023)

Disperse Hypergraphs
por: Gishboliner, Lior, et al.
Publicado: (2025)

Bisection Width, Discrepancy, and Eigenvalues of Hypergraphs
por: Räty, Eero, et al.
Publicado: (2024)

A Hypergraph Container Method on Spread SAT: Approximation and Speedup
por: Han, Zicheng, et al.
Publicado: (2026)

Refuting Perfect Matchings in Spectral Expanders is Hard
por: Biswas, Ari, et al.
Publicado: (2025)

Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems
por: Gribanov, Dmitry, et al.
Publicado: (2022)

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
por: Li, Xin, et al.
Publicado: (2023)

Optimal Union Probability Interval Is NP-Hard
por: Kaski, Petteri, et al.
Publicado: (2026)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
por: Dhawan, Abhishek, et al.
Publicado: (2024)

Parameterised Holant Problems
por: Aivasiliotis, Panagiotis, et al.
Publicado: (2024)

The Rank-Ramsey Problem and the Log-Rank Conjecture
por: Beniamini, Gal, et al.
Publicado: (2024)

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
por: Hsieh, Jun-Ting, et al.
Publicado: (2024)

Hardness of Finding Kings and Strong Kings
por: Alaoui, Ziad Ismaili, et al.
Publicado: (2025)

Determining the Outerthickness of Graphs Is NP-Hard
por: Lee, Pin-Hsian, et al.
Publicado: (2026)

On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
por: Borzechowski, Michaela, et al.
Publicado: (2023)

The Complexity Classes of Hamming Distance Recoverable Robust Problems
por: Grüne, Christoph
Publicado: (2022)

King Chasing Problem in Chinese Chess is NP-hard
por: Li, Chao, et al.
Publicado: (2026)

Hypergraph Samplers: Typical and Worst Case Behavior
por: Alev, Vedat Levi, et al.
Publicado: (2026)

Hardness of 4-Colourings G-Colourable Graphs
por: Avvakumov, Sergey, et al.
Publicado: (2025)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
por: Baril, Ambroise, et al.
Publicado: (2024)

Testing Sumsets is Hard
por: Chen, Xi, et al.
Publicado: (2024)

Real Stability and Log Concavity are coNP-Hard
por: Chin, Tracy
Publicado: (2024)

Deciding if a DAG is Interesting is Hard
por: De Carufel, Jean-Lou, et al.
Publicado: (2025)

Graph Irregularity via Edge Deletions
por: Bensmail, Julien, et al.
Publicado: (2025)

The Chromatic Number of Kneser Hypergraphs via Consensus Division
por: Haviv, Ishay
Publicado: (2023)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
por: Lee, Euiwoong, et al.
Publicado: (2024)

On Computational Aspects of Ordered Matching Problems
por: Čertík, Michal, et al.
Publicado: (2025)

Reinforced Generation of Combinatorial Structures: Hardness of Approximation
por: Nagda, Ansh, et al.
Publicado: (2025)

The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits
por: Mondada, Luca, et al.
Publicado: (2023)

Learning Read-Once Determinants and the Principal Minor Assignment Problem
por: Aravind, Abhiram, et al.
Publicado: (2026)

Efficient approximation schemes for scheduling on a stochastic number of machines
por: Epstein, Leah, et al.
Publicado: (2024)

A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem
por: Li, Zhengyu, et al.
Publicado: (2023)

Kernelization Complexity of Solution Discovery Problems
por: Grobler, Mario, et al.
Publicado: (2024)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
por: Eagling-Vose, Tala, et al.
Publicado: (2025)

Monotone Circuit Complexity of Matching
por: Cavalar, Bruno, et al.
Publicado: (2025)