Decision versions of optimization problems: cardinality constraint (lower bound) as a CNF Horn formula for Maximum Matching

Prabhu Manyem

We provide a formula for the lower bound in the form of $|F|\ge K$, in such a way that the decision version of unweighted non-bipartite matching can be solved in polynomial time.…