+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +**********************************************************************
Zeit: Montag, 16. November 2020, 13:00 Uhr Zoom: https://rwth.zoom.us/j/94172280001?pwd=K2Z6Z1ZHbUVVdDBDbjNSWVBVUTZoZz09
Meeting ID: 941 7228 0001 Passcode: N.gdJ5
Referent: Jan Dreier, M.Sc. Lehr- und Forschungsgebiet Theoretische Informatik
Thema: Two New Perspectives on Algorithmic Meta-Theorems
Abstract:
We present two algorithmic meta-theorems. Our first meta-theorem is an approximation scheme of the parameterized model-checking problem for the first-order counting logic FO({>0}). This logic extends first-order logic with the ability to count the number of satisfying assignments of a variable and compare it to fixed but arbitrarily large numbers. The model-checking scheme runs in linear fpt time (parameterized by formula length) on structures with bounded expansion and either gives the correct answer or says ``I do not know.'' The latter answer may only be given if small perturbations in the number-symbols of the formula could make it both satisfied and unsatisfied. As a consequence, every property expressible in FO({>0}) can be approximated in linear time on bounded expansion graph classes. A restricted set of counting properties can also be solved exactly in linear time, leading for example to an fpt algorithm for partial dominating set on bounded expansion graph classes. These results are complemented by showing that exactly solving the model-checking problem for FO({>0}) is already hard on trees of bounded depth and just slightly increasing the expressiveness of FO({>0}) makes even approximation hard on trees.
Our second meta-theorem is a first-order model-checking algorithm for random graphs and complex networks. Roughly speaking, we say a random graph model is alpha-power-law-bounded if it is unclustered and the fraction of vertices with degree k is O(k^-alpha). We solve the parameterized first-order model-checking problem in almost linear fpt time on random graph models satisfying this property with alpha >= 3. This means in particular that one can solve every first-order property in almost linear expected time on these random graph models. This includes many popular models of complex networks such as preferential attachment graphs, Chung–Lu graphs, configuration graphs, and sparse Erdős–Rényi graphs. We present hardness results that show intractability for alpha < 3, assuming we allow an adversary to color the vertices of the input graph. We base our algorithms on a new structural decomposition of alpha-power-law-bounded random graphs and on new concentration bounds for the degree evolution in preferential attachment graphs.
Es laden ein: die Dozentinnen und Dozenten der Informatik