10 citations · 12 across the 4 of their papers we have counts for
5 papers
A Definability Dichotomy for Finite Valued CSPs
Anuj Dawar, Pengming Wang
Finite valued constraint satisfaction problems are a formalism for describing many natural optimization problems, where constraints on the values that variables can take come with…
Fixed-parameter Tractable Distances to Sparse Graph Classes
Jannis Bulian, Anuj Dawar
We show that for various classes C of sparse graphs, and several measures of distance to such classes (such as edit distance and elimination distance), the problem of determining t…
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…
Domination Problems in Nowhere-Dense Classes of Graphs
Anuj Dawar, Stephan Kreutzer
We investigate the parameterized complexity of generalisations and variations of the dominating set problem on classes of graphs that are nowhere dense. In particular, we show that…
Homomorphism Preservation on Quasi-Wide Classes
Anuj Dawar
A class of structures is said to have the homomorphism-preservation property just in case every first-order formula that is preserved by homomorphisms on this class is equivalent t…