“Global” graph problems tend to be intractable

摘要

A notion of “information-flow complexity” is used to formally measure the degree to which a graph problem is a “global” problem (in the sense of “global” vs. “local” optimization). Under this measure a number of intractable problems including VERTEX COVER, GRAPH 3-COLORABILITY, HAMILTONIAN CIRCUIT, and other NP-complete problems are exponentially more “global” than a number of tractable problems including EDGE COVER, GRAPH 2-COLORABILITY, EULERIAN CIRCUIT, and other problems in P.