Graphs with Bounded Treewidth and Complexity of Restricted Discrete Optimization Problems

一类NP难离散问题的具体复杂性行为 优化问题将进行调查，与实例 仅限于具有树可表示结构的图（对于 实例、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.