Parameterized complexity: A framework for systematically confronting computational intractability
Parameterized complexity: A framework for systematically confronting computational intractability
复制标题
DOI：
10.1090/dimacs/049/04
复制
发表时间：
1997
期刊：
影响因子：
5.5
通讯作者：
R. Downey;M. Fellows;U. Stege
中科院分区：
文献类型：
--
作者：
R. Downey;M. Fellows;U. Stege
在本文中，我们给出了一个程序化的概述参数化的计算复杂性的广泛背景下的问题，处理计算的棘手性。我们给出了一些例子，说明xed参数易处理性技术如何以两种不同的方式提供实用算法：（1）通过为小参数范围提供有用的精确算法，以及（2）通过为启发式算法的设计提供指导。特别地，我们描述了一个改进的FPT核化算法的顶点覆盖，一个实用的FPT算法的最大协议子树（MAST）问题的参数化的物种数被删除，和新的一般算法这些问题的FPT技术的基础上。在进行概述的过程中，我们还研究了一些结构和硬度问题。本文证明了人工智能中一个重要的自然参数化问题--规划问题（其中参数是规划的大小）对于W1是完备的。作为推论，这意味着Petri网的k步可达性对于W1]是完全的。我们描述了如何树宽的概念可以应用到FPT规划和其他问题的逻辑，以获得FPT的结果。我们描述了一个令人惊讶的结构性结果，关于顶端的参数化的复杂性层次结构：自然参数化的图k-着色问题不能解决相对于XP无论是通过显示XP的成员资格，或通过显示XP的硬度，而不解决P = NP问题的一种或另一种方式。
In this paper we give a programmatic overview of parame-terized computational complexity in the broad context of the problem of coping with computational intractability. We give some examples of how xed-parameter tractability techniques can deliver practical algorithms in two diierent ways: (1) by providing useful exact algorithms for small parameter ranges, and (2) by providing guidance in the design of heuristic algorithms. In particular, we describe an improved FPT ker-nelization algorithm for Vertex Cover, a practical FPT algorithm for the Maximum Agreement Subtree (MAST) problem parameterized by the number of species to be deleted, and new general heuristics for these problems based on FPT techniques. In the course of making this overview, we also investigate some structural and hardness issues. We prove that an important naturally parameterized problem in artiicial intelligence, STRIPS Planning (where the parameter is the size of the plan) is complete for W1]. As a corollary, this implies that k-Step Reachability for Petri Nets is complete for W1]. We describe how the concept of treewidth can be applied to STRIPS Planning and other problems of logic to obtain FPT results. We describe a surprising structural result concerning the top end of the parameterized complexity hierarchy: the naturally parameterized Graph k-Coloring problem cannot be resolved with respect to XP either by showing membership in XP, or by showing hardness for XP without settling the P = NP question one way or the other.