Existential Second Order Logic Expression With Horn First Order for Maximum Clique (Decision Version)

Prabhu Manyem

We show that the maximum clique problem (decision version) can be expressed in existential second order (ESO) logic, where the first order part is a Horn formula in second-order qu…