### Existential second-order logic over graphs: Charting the tractability frontierExistential second-order logic over graphs: Charting the tractability frontier

Access Restriction
Subscribed

 Author Gottlob, Georg ♦ Kolaitis, Phokion G. ♦ Schwentick, Thomas Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2004 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Existential second-order logic ♦ NP-complete problems ♦ Finite model theory ♦ Graph coloring ♦ Graph constraints ♦ Prefix classes Abstract Fagin's theorem, the first important result of descriptive complexity, asserts that a property of graphs is in NP if and only if it is definable by an existential second-order formula. In this article, we study the complexity of evaluating existential second-order formulas that belong to prefix classses of existential second-order logic, where a prefix class is the collection of all existential second-order formulas in prenex normal form such that the second-order and the first-order quantifiers obey a certain quantifier pattern. We completely characterize the computational complexity of prefix classes of existential second-order logic in three different contexts: (1) over directed graphs, (2) over undirected graphs with self-loops and (3) over undirected graphs without self-loops. Our main result is that in each of these three contexts a $\textit{dichotomy}$ holds, that is to say, each prefix class of existential second-order logic either contains sentences that can express NP-complete problems, or each of its sentences expresses a polynomial-time solvable problem. Although the boundary of the dichotomy coincides for the first two cases, it changes, as one moves to undirected graphs without self-loops. The key difference is that a certain prefix class, based on the well-known Ackermann class of first-order logic, contains sentences that can express NP-complete problems over graphs of the first two types, but becomes tractable over undirected graphs without self-loops. Moreover, establishing the dichotomy over undirected graphs without self-loops turns out to be a technically challenging problem that requires the use of sophisticated machinery from graph theory and combinatorics, including results about graphs of bounded tree-width and Ramsey's theorem. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2004-03-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 51 Issue Number 2 Page Count 51 Starting Page 312 Ending Page 362

#### Open content in new tab

Source: ACM Digital Library