Robust Algorithms for Restricted Domains

有时，限制感兴趣的领域会使难题变得容易。例如，即使一般问题是np困难的，人们也可以在多项式时间内找到二部图的最小顶点覆盖。有时，限制域并不能使问题变得更容易。例如，寻找一个平面图形的最小顶点覆盖是np困难的。这个项目是研究与问题相关的问题，这些问题的实例来自于通过对更一般的类的自然限制而获得的类。在处理这类问题时自然产生的许多微妙之处，在文献中都被掩盖了。也许在受限类上解决问题的最常见解释是“承诺”版本，其中保证输入在类中，并且如果不满足此保证，则“解决”问题的算法不必正确运行（甚至终止）。本研究基于不同的定义，即即使输入不属于受限类，算法也必须产生正确的输出；这样的输出可能是“输入不在类中”，也可能是问题的正确解决方案。在受限域上解决问题的新定义要求算法“健壮”：面对无效输入，这是比“不关心”更严格的要求。鲁棒算法可以作为更通用算法的构建块进行操作；相比之下，“承诺”算法则不是。此外，还存在一些问题，这些问题在解决问题的“承诺”版本中属于P，而在新定义下属于NP-hard。可以提出的论点是，硬度结果有时更有意义，需要对受限类np完备性的概念进行修改。图类提供有趣和自然的受限域；本项目还将研究许多关于图类的问题，这些问题满足两个要求：给定图（即“模型”）的特殊而自然的表示，易于求解。如果图以一般形式（如邻接表）给出，则在复杂度方面是开放的。虽然这些开放问题中的一些看起来相当困难，但它们并不容易被归类为“真正”困难。这是因为模型提供了一个证明，证明问题属于NP和co-NP；因此，只有当NP = co-NP时，这些问题才可能是NP困难的。有几个这样的问题需要一个可操作性的概念，该项目将调查各种可能性

Sometimes, restricting the domain of interest makes a hard problem easy. For example, one can find the minimum vertex cover of a bipartite graph in polynomial time even though the general problem is NP-hard. Sometimes, restricting the domain does not make a problem easier. For example, finding the minimum vertex cover of a planar graph is NP-hard. This project is to study issues relating to problems whose instances come from classes obtained by natural restrictions on more general classes. Many subtleties which arise naturally in dealing with such problems have been glossed over in the literature. Perhaps the most common interpretation of solving a problem on a retricted class is the "promise" version, in which there is a guarantee that the input is in the class, and an algorithm to "solve" the problem need not function correctly (or even terminate) if this guarantee is not met. This research is based on different definition, one in which the algorithm must produce correct output even if the input is not in the restricted class; such output may either be "the input is not in the class" or the correct solution to the problem. The new definition of solving proglems on restricted domains requires algorithms to be "robust: in the face of invalid input, a more stringent requirement than "don't care." Robust algorithms are amenable to manipulation as building blocks of more general algorithms; in contrast, "promise" algorithms are not. Furthermore, there exist problems which are in P in the "promise" version of solving a problem, while being NP-hard under the new definition. Arguments can be made that the hardness results are sometimes more meaningful, necessitating a revamping of the notion of restricted class NP-completeness. Graph classes provide interesting and natural restricted domains; the project will also study many problems on graph classes which satisfy the twin requirements of being:. Easy to solve given a special and natural representation of a graph (i.e., a "model"). Open with respect to complexity if the graph is given in a general form such as an adjacency list.While some of these open problems appear to be quite hard, they are not easily classifiable as "really" being hard. This is because the model provides a certificate for the problem to be in NP and in co-NP; consequently, such problems can be NP-hard only if NP = co-NP. An operational notion of intractability is needed for several such problems and the project will investigate possibilities