Maximum Matching and Linear Programming in Fixed-Point Logic with Counting

Matthew Anderson, Anuj Dawar, Bjarki Holm

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…