Robust Algorithms for Restricted Domains

有时，限制兴趣领域会使难题变得容易。 例如，即使一般问题是NP-困难的，也可以在多项式时间内找到二分图的最小顶点覆盖。 有时，限制域并不能使问题变得更容易。 例如，求平面图的最小顶点覆盖是NP-困难的。 这个项目是研究与问题有关的问题，这些问题的实例来自于对更一般的类的自然限制。 在处理这些问题时自然产生的许多微妙之处在文献中被掩盖了。 也许在受限类上解决问题最常见的解释是“promise”版本，其中保证输入在类中，如果不满足此保证，则“解决”问题的算法不需要正确运行（甚至终止）。 本研究基于不同的定义，其中一个算法必须产生正确的输出，即使输入不在受限类中;这样的输出可能是“输入不在类中”或问题的正确解决方案。 在有限域上求解问题的新定义要求算法是“鲁棒的：面对无效输入，这是比“不关心”更严格的要求。鲁棒算法可以作为更通用算法的构建块进行操作;相反，“承诺”算法则不然。 此外，还存在一些问题，这些问题在解决问题的“promise”版本中是P中的，而在新定义下是NP-难的。 可以提出的论点是，硬度的结果有时更有意义，有必要修改的概念，限制类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