New perspectives on semiring applications to dynamic programming

doi:10.1016/j.dam.2025.12.035

2025-12-01

Baril, Ambroise

Miguel Couceiro

Lagerkvist, Victor *

DOI：10.1016/j.dam.2025.12.035

原文链接

查看原文

摘要

En 中文

半环代数已被证明为形式化许多值得注意的组合问题的合适语言。例如，当应用于热带半环时，最短路径问题可被视为代数路径问题的特例。半环的应用通常使得在不增加计算复杂性的情况下解决扩展问题成为可能。本文进一步探索利用半环代数通过动态规划处理和解决经典计算问题的几个扩展。我们考虑一种通用方法，允许我们为具有合理证明概念（例如NP问题）的任何问题定义半环扩展。这使得我们可以考虑这些组合问题的成本变体，以及它们的计数扩展，其中目标是确定给定问题接受多少个解。该方法对半环结构不做特殊假设（例如幂等性）。我们还提出了一种新的半环结合代数运算，称为三角积，它使我们的动态规划算法能够计算最小成本的解的数量。我们通过两个计算上非常不同但广为人知的NP难问题，即连通支配集问题和有限域约束满足问题（CSPs），来说明我们框架的优势。特别地，我们证明了相对于输入的团宽和树宽的固定参数可解性（FPT）。这也使我们能够计算最小成本的解，而这在文献中是一个被忽视的问题。(c) 2025 Published by Elsevier B.V.

Keyword:

Semiring

Dynamic programming

Fixed parameter tractability

Constraint satisfaction problems

Connected dominating set