First-Order Model-Checking in Random Graphs and Complex Networks

arXiv (Cornell University)

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 $α\ge 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.

Authors 3

1. Jan Dreier Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen University, Germany

   RWTH Aachen University

2. Philipp Kuinke Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen University, Germany

   RWTH Aachen University

3. Peter Rossmanith Aachen Department of Computer Science

   RWTH Aachen University

   Affiliation as printed

   Department of Computer Science, RWTH Aachen University, Germany

   RWTH Aachen University