综述:流动增强技术的应用

《Computer Science Review》:Applications of flow-augmentation

【字体: 大 中 小 】 时间:2025年12月22日 来源:Computer Science Review 12.7

编辑推荐:

  斯特凡·克拉奇(Stefan Kratsch)| 马尔钦·皮利普丘克(Marcin Pilipczuk)| 罗哈尼·夏尔马(Roohani Sharma)| 马格努斯·瓦尔斯特伦(Magnus Wahlstr?m) 柏林洪堡大学(Humboldt-Universit?t zu

  斯特凡·克拉奇(Stefan Kratsch)| 马尔钦·皮利普丘克(Marcin Pilipczuk)| 罗哈尼·夏尔马(Roohani Sharma)| 马格努斯·瓦尔斯特伦(Magnus Wahlstr?m)
柏林洪堡大学(Humboldt-Universit?t zu Berlin),德国柏林

**摘要**
流量增强(Flow-augmentation)是一种最近引入的技术,适用于设计图分割问题的参数化算法。它被认为是我们理解有向图中图分割问题参数化复杂性领域的关键组成部分,并且在约束满足问题(Constraint Satisfaction Problems, CSPs)领域中也找到了许多应用。在这篇综述中,我们介绍了该技术及其主要应用。由于它的许多应用都与约束满足问题相关,我们还借此机会探讨了按解成本参数化的MinCSP问题的参数化复杂性现状——即对于哪些CSP语言来说,判断是否存在一个满足除至多k个约束之外的所有约束的解是FPT(可多项式时间解决)的。

**图分割问题**
按解大小进行参数化一直是参数化复杂性研究的核心主题。在图分割问题中也是如此。我们将广泛理解“分割问题”的概念:图分割问题要求从给定的图中移除一小部分,以实现所需的分割属性。典型的例子是最小割问题(Minimum Cut problem):给定一个图G和两个不同的顶点s, t ∈ V(G),我们希望找到最小的割。

**约束满足问题**
从约束满足问题的角度来审视前面讨论的示例问题会提供一个更广泛且非常有用的视角。
约束满足问题(简称CSPs)是一个非常通用的框架,涵盖了许多计算问题。通常,一个CSP实例包括一组变量X,对于每个变量x属于X,有一个称为x的域的集合Dx,以及一个约束的多重集C。每个约束C属于C,由一个变量元组tC和一个关系RC ? …组成(具体关系取决于语言)。

**布尔情况下的二分法**
在本节中,我们讨论了布尔情况下MinCSP和Weighted MinCSP在FPT(多项式时间可解)和W[1]-hard(难以多项式时间解决)之间的二分法。
**定理3.1 (布尔语言的)Weighted MinCSP二分定理**
[31]
对于每个有限的布尔语言Γ,如果SAT(Γ)可以在多项式时间内解决,那么MinCSP(Γ)的参数化复杂性(按违反的约束数量参数化)属于以下类别之一:
- Weighted MinCSP(Γ)是FPT;
- MinCSP(Γ)是FPT,但其加权版本是W[1]-hard;
- MinCSP(Γ)是W[1]-hard。
定理3.1有两个有趣的特性。

**加权图分割问题的参数化复杂性**
本节的目标是提供一个完整的图(加权版本)基本分割问题参数化复杂性图景,当参数为解大小时。我们首先关注有向图中的加权图分割问题。这里的经典问题是双标准最小割问题(Bicriteria Minimum Cut),通过简单应用流量增强技术,在定理1.7中被证明是FPT。除此之外,在第1.5节中我们还看到了Weighted ?-Chain线性方程的FPT算法。

**线性方程的CSPs**
现在我们(尝试)离开图问题,讨论另一个领域的CSPs,即输入是一组线性方程的MinCSP问题。本节主要基于Dabrowski等人[23]的研究以及最近预印本[24]中的部分结果。

**背景介绍**
为了说明背景,让我们先定义一些基本概念。我们不需要任何特殊结构,但建立基础是有帮助的。回忆一下,环是一种定义在元素集合R上的代数结构,配备了加法运算。

**时间型CSPs**
在本节中,我们关注域为Q的约束满足问题,Q通过谓词<、≤、=、≠进行访问。也就是说,域是一个无限且稠密的完全序。这类CSP在文献中通常被称为时间型CSPs。“时间型”这个名称来源于这样的动机:域Q代表时间线,变量是要在时间线上安排的事件。例如,(x < y)表示x需要在y之前被安排,x = y表示x和y需要同时被安排。

**利益冲突声明**
作者声明他们没有已知的可能会影响本文所述工作的财务利益或个人关系。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号