5 papers
New Perspectives on Semiring Applications to Dynamic Programming
Ambroise Baril, Miguel Couceiro, Victor Lagerkvist
Semiring algebras have been shown to provide a suitable language to formalize many noteworthy combinatorial problems. For instance, the Shortest-Path problem can be seen as a speci…
Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
Ambroise Baril, Miguel Couceiro, Victor Lagerkvist
The -Coloring problem is a well-known generalization of the classical NP-complete problem -Coloring where the task is to determine whether an input graph admits a homomorphis…
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).…
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…
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…