3 papers
cs.CC2024
The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
Ambroise Baril, Miguel Couceiro, Victor Lagerkvist
In this paper we are interested in the fine-grained complexity of deciding whether there is a homomorphism from an input graph to a fixed graph (the -Coloring problem).…
cs.CC2023
On the Parameterized Complexity of Relaxations of Clique
Ambroise Baril, Antoine Castillon, Nacim Oijid
We investigate the parameterized complexity of several problems formalizing cluster identification in graphs. In other words we ask whether a graph contains a large enough and suff…
cs.CC2022
Component twin-width as a parameter for BINARY-CSP and its semiring generalisations
Ambroise Baril, Miguel Couceiro, Victor Lagerkvist
We investigate the fine-grained and the parameterized complexity of several generalizations of binary constraint satisfaction problems (BINARY-CSPs), that subsume variants of graph…