New Perspectives on Semiring Applications to Dynamic Programming Article Swipe

MAKE IMPACT

Baril, Ambroise , Couceiro, Miguel , Lagerkvist, Victor · YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2512.03916

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 special case of the Algebraic-Path problem when applied to the tropical semiring. The application of semirings typically makes it possible to solve extended problems without increasing the computational complexity. In this article we further exploit the idea of using semiring algebras to address and tackle several extensions of classical computational problems by dynamic programming. We consider a general approach which allows us to define a semiring extension of any problem with a reasonable notion of a certificate (e.g., an NP problem). This allows us to consider cost variants of these combinatorial problems, as well as their counting extensions where the goal is to determine how many solutions a given problem admits. The approach makes no particular assumptions (such as idempotence) on the semiring structure. We also propose a new associative algebraic operation on semirings, called $Δ$-product, which enables our dynamic programming algorithms to count the number of solutions of minimal costs. We illustrate the advantages of our framework on two well-known but computationally very different NP-hard problems, namely, Connected-Dominating-Set problems and finite-domain Constraint Satisfaction Problems (CSPs). In particular, we prove fixed parameter tractability (FPT) with respect to clique-width and tree-width of the input. This also allows us to count solutions of minimal cost, which is an overlooked problem in the literature.

Type

preprint

Landing Page

https://doi.org/10.48550/arxiv.2512.03916

OA Status

green

OpenAlex ID

https://openalex.org/W7108781982

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W7108781982

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2512.03916

Digital Object Identifier

Title

New Perspectives on Semiring Applications to Dynamic Programming

Work title

Type

preprint

OpenAlex work type

Publication year

2025

Year of publication

Publication date

2025-12-03

Full publication date if available

Authors

Baril, Ambroise, Couceiro, Miguel, Lagerkvist, Victor

List of authors in order

Landing page

https://doi.org/10.48550/arxiv.2512.03916

Publisher landing page

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://doi.org/10.48550/arxiv.2512.03916

Direct OA link when available

Concepts

Semiring, Mathematics, Constraint programming, Constraint satisfaction problem, Dynamic programming, Associative property, Theoretical computer science, Computer science, Multiset, Algebraic number, Algebra over a field, Constraint (computer-aided design), Extension (predicate logic), Certificate, Lexicographical order, Algebraic structure, Mathematical optimization, Duality (order theory), Computation, Constraint satisfaction, Optimization problem, Computational complexity theory, Kleene algebra, Exploit, Discrete mathematics, Unification, Algorithm

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Full payload