License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.40
URN: urn:nbn:de:0030-drops-129068
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12906/
Dreier, Jan ;
Kuinke, Philipp ;
Rossmanith, Peter
First-Order Model-Checking in Random Graphs and Complex Networks
Abstract
Complex networks are everywhere. They appear for example in the form of biological networks, social networks, or computer networks and have been studied extensively. Efficient algorithms to solve problems on complex networks play a central role in today’s society. Algorithmic meta-theorems show that many problems can be solved efficiently. Since logic is a powerful tool to model problems, it has been used to obtain very general meta-theorems. In this work, we consider all problems definable in first-order logic and analyze which properties of complex networks allow them to be solved efficiently.
The mathematical tool to describe complex networks are random graph models. We define a property of random graph models called α-power-law-boundedness. Roughly speaking, a random graph is α-power-law-bounded if it does not admit strong clustering and its degree sequence is bounded by a power-law distribution with exponent at least α (i.e. the fraction of vertices with degree k is roughly O(k^{-α})).
We solve the first-order model-checking problem (parameterized by the length of the formula) in almost linear FPT time on random graph models satisfying this property with α ≥ 3. This means in particular that one can solve every problem expressible in first-order logic in almost linear expected time on these random graph models. This includes for example preferential attachment graphs, Chung-Lu graphs, configuration graphs, and sparse Erdős-Rényi graphs. Our results match known hardness results and generalize previous tractability results on this topic.
BibTeX - Entry
@InProceedings{dreier_et_al:LIPIcs:2020:12906,
author = {Jan Dreier and Philipp Kuinke and Peter Rossmanith},
title = {{First-Order Model-Checking in Random Graphs and Complex Networks}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {40:1--40:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-162-7},
ISSN = {1868-8969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12906},
URN = {urn:nbn:de:0030-drops-129068},
doi = {10.4230/LIPIcs.ESA.2020.40},
annote = {Keywords: random graphs, average case analysis, first-order model-checking}
}
|
Keywords: |
|
random graphs, average case analysis, first-order model-checking |
|
Collection: |
|
28th Annual European Symposium on Algorithms (ESA 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
26.08.2020 |
