Graphs with Bounded Treewidth and Complexity of Restricted Discrete Optimization Problems

一些NP-hard离散优化问题的具体复杂性行为将被研究，实例仅限于具有树表示结构的图（例如，k-树，序列-并行图或间隔图）。本研究的一个主要工具是图的树宽度概念。有界树宽图族允许一种特殊类型的非串行动态规划方法，导致算法有效地解决许多困难的离散优化问题。Robertson和Seymour关于图的井-拟序的工作表明，当实例被限制在广泛的图类时，存在许多固有困难的优化问题的低阶多项式时间解算法。然而，这样的算法有两个弱点：它们需要有限障碍集的知识，而且一般的设计范式构建的算法在多项式时间内执行，但具有天文数量级的乘法常数。提出的研究将通过两种方式解决这些缺陷：研究为具有均匀有界树宽的图族构建障碍集的方法，以及简化特定离散优化问题的求解算法，因为算法设计范式的完全通用性通常是不必要的。

The concrete complexity behavior of some NP-hard discrete optimization problems will be investigated, with instances restricted to graphs having tree-representable structure (for instance, k-trees, series-parallel graphs, or interval graphs.) A major tool in this research is the concept of treewidth of graphs. Families of graphs with bounded treewidth admit a special type of non-serial dynamic programming approach leading to algorithms efficiently solving many difficult discrete optimization problems. The work of Robertson and Seymour on well-quasi orderings of graphs implies existence of low-order polynomial time solution algorithms for many inherently difficult optimization problems, when instances are restricted to wide classes of graphs. However, such algorithms suffer a double weakness: they require knowledge of a finite obstruction set, and the general design paradigm constructs algorithms that execute in polynomial time but with multiplicative constants of astronomic magnitude. The proposed research will deal with these deficiencies in two ways: investigating means to construct obstruction sets for families of graphs with uniformly bounded treewidth and streamlining solution algorithms for particular discrete optimization problems, as the full generality of the algorithm design paradigm often is not necessary.