On universally easy classes for NP-complete problems
Erik D. Demaine, Alejandro López-Ortíz, J. Ian Munro · 2001
We explore the natural question of whether all NP- complete problems have a common restriction under which they are polynomially solvable. More precisely, we study what languages are universally easy in that their intersection with any NP-complete problem is in P. In particular, we give a polynomial-time algorithm to determine whether a regular language is universally easy. While our approach is language-theoretic, the results bear directly on nding polynomial-time solutions to very broad and useful classes of problems. 1 Introduction and Overview Empirically, it has been observed that some classes of instances result in polynomial-time algorithms for what are otherwise NP-complete problems. For example, colouring, clique and independent set are wellknown NP-complete problems that have polynomialtime solutions when restricted to interval graphs [7]. But this property is not universal: list coloring in graphs and determining the existence of k vertex-disjoint paths (where k is part ...