  We establish the expressibility in fixed-point logic with counting (FPC) of a
number of natural polynomial-time problems. In particular, we show that the
size of a maximum matching in a graph is definable in FPC. This settles an open
problem first posed by Blass, Gurevich and Shelah, who asked whether the
existence of perfect matchings in general graphs could be determined in the
more powerful formalism of choiceless polynomial time with counting. Our result
is established by showing that the ellipsoid method for solving linear programs
can be implemented in FPC. This allows us to prove that linear programs can be
optimised in FPC if the corresponding separation oracle problem can be defined
in FPC. On the way to defining a suitable separation oracle for the maximum
matching problem, we provide FPC formulas defining maximum flows and canonical
minimum cuts in capacitated graphs.

Logic in Computer Science;Computational Complexity;Discrete Mathematics