3 papers
cs.CC2025
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…
cs.CC2025
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…
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).…