Domination Problems in Nowhere-Dense Classes

摘要: We investigate the parameterized complexity of generalisations and variations of dominating set problem on classes graphs that are nowhere dense. In particular, we show distance-$d$ dominating-set problem, also known as $(k,d)$-centres is fixed-parameter tractable any class that is dense closed under induced subgraphs. This generalises known results about $H$-minor free classes, classes with locally excluded minors bounded expansion. A key feature our proof it based simply fact these graph uniformly quasi-wide, does not rely a structural decomposition. Our result establishes distance-$d$ dominating-set FPT expansion, answering a question Ne{\v s}et{\v r}il Ossona de Mendez.