Buchumschlag

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Baril, Ambroise, Couceiro, Miguel, Lagerkvist, Victor
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity Combinatorics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
von: Baril, Ambroise, et al.
Veröffentlicht: (2025)

New Perspectives on Semiring Applications to Dynamic Programming
von: Baril, Ambroise, et al.
Veröffentlicht: (2025)

Complexity Aspects of Homomorphisms of Ordered Graphs
von: Čertík, Michal, et al.
Veröffentlicht: (2025)

The Rank-Ramsey Problem and the Log-Rank Conjecture
von: Beniamini, Gal, et al.
Veröffentlicht: (2024)

Reconfiguring Graph Homomorphisms on the Sphere
von: Lee, Jae-Baek, et al.
Veröffentlicht: (2018)

A Fine-Grained Complexity View on Propositional Abduction -- Algorithms and Lower Bounds
von: Lagerkvist, Victor, et al.
Veröffentlicht: (2025)

On the Keevash-Knox-Mycroft Conjecture
von: Gan, Luyining, et al.
Veröffentlicht: (2022)

The Complexity Classes of Hamming Distance Recoverable Robust Problems
von: Grüne, Christoph
Veröffentlicht: (2022)

The Richness of CSP Non-redundancy
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2025)

The Log-Rank Conjecture: New Equivalent Formulations
von: Hambardzumyan, Lianna, et al.
Veröffentlicht: (2025)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
von: Eagling-Vose, Tala, et al.
Veröffentlicht: (2025)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
von: Mu, Ta-Yu, et al.
Veröffentlicht: (2024)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
von: Roberson, David E., et al.
Veröffentlicht: (2023)

Fine-Grained Cryptanalysis: Tight Conditional Bounds for Dense k-SUM and k-XOR
von: Dinur, Itai, et al.
Veröffentlicht: (2021)

Parameterised Holant Problems
von: Aivasiliotis, Panagiotis, et al.
Veröffentlicht: (2024)

A General Framework for Low Soundness Homomorphism Testing
von: Mittal, Tushant, et al.
Veröffentlicht: (2025)

The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits
von: Mondada, Luca, et al.
Veröffentlicht: (2023)

Hardness of Hypergraph Edge Modification Problems
von: Gishboliner, Lior, et al.
Veröffentlicht: (2025)

Monotone Circuit Complexity of Matching
von: Cavalar, Bruno, et al.
Veröffentlicht: (2025)

Kernelization Complexity of Solution Discovery Problems
von: Grobler, Mario, et al.
Veröffentlicht: (2024)

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
von: Seppelt, Tim
Veröffentlicht: (2024)

A Note on the Complexity of Directed Clique
von: Gutowski, Grzegorz, et al.
Veröffentlicht: (2026)

On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
von: Borzechowski, Michaela, et al.
Veröffentlicht: (2023)

King Chasing Problem in Chinese Chess is NP-hard
von: Li, Chao, et al.
Veröffentlicht: (2026)

Communication Complexity of Disjointness under Product Distributions
von: Hunter, Zach, et al.
Veröffentlicht: (2026)

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
von: Seppelt, Tim
Veröffentlicht: (2023)

Lions and Contamination: Trees and General Graphs
von: Kim, Dohoon, et al.
Veröffentlicht: (2026)

On a Hierarchy of Spectral Invariants for Graphs
von: Arvind, V., et al.
Veröffentlicht: (2023)

On the Structure of Hamiltonian Graphs with Small Independence Number
von: Jedličková, Nikola, et al.
Veröffentlicht: (2024)

On the Nature and Complexity of an Impartial Two-Player Variant of the Game Lights-Out
von: Fiorini, Eugene, et al.
Veröffentlicht: (2024)

Direct Product Primality Testing of Graphs is GI-hard
von: Calderoni, Luca, et al.
Veröffentlicht: (2020)

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

Graph Search Trees and the Intermezzo Problem
von: Beisegel, Jesse, et al.
Veröffentlicht: (2024)

On Computational Aspects of Ordered Matching Problems
von: Čertík, Michal, et al.
Veröffentlicht: (2025)

On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems
von: Scheffler, Robert
Veröffentlicht: (2025)

Complexity of Faceted Explanations in Propositional Abduction
von: Schmidt, Johannes, et al.
Veröffentlicht: (2025)

Structural Origins of Cubic Complexity in Pebble Motion
von: Nakamigawa, Tomoki, et al.
Veröffentlicht: (2025)

CSPs with Few Alien Constraints
von: Jonsson, Peter, et al.
Veröffentlicht: (2024)

Learning Read-Once Determinants and the Principal Minor Assignment Problem
von: Aravind, Abhiram, et al.
Veröffentlicht: (2026)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
von: Komarath, Balagopal, et al.
Veröffentlicht: (2025)