Dreier, Jan ;
Lotze, Henri ;
Rossmanith, Peter
Hard Problems on Random Graphs
Abstract
Many graph properties are expressible in first order logic. Whether a graph contains a clique or a dominating set of size k are two examples. For the solution size as its parameter the first one is W[1]complete and the second one W[2]complete meaning that both of them are hard problems in the worstcase. If we look at both problem from the aspect of averagecase complexity, the picture changes. Clique can be solved in expected FPT time on uniformly distributed graphs of size n, while this is not clear for Dominating Set. We show that it is indeed unlikely that Dominating Set can be solved efficiently on random graphs: If yes, then every firstorder expressible graph property can be solved in expected FPT time, too. Furthermore, this remains true when we consider random graphs with an arbitrary constant edge probability. We identify a very simple problem on random matrices that is equally hard to solve on average: Given a square boolean matrix, are there k rows whose logical AND is the zero vector? The related Even Set problem on the other hand turns out to be efficiently solvable on random instances, while it is known to be hard in the worstcase.
BibTeX  Entry
@InProceedings{dreier_et_al:LIPIcs:2020:12447,
author = {Jan Dreier and Henri Lotze and Peter Rossmanith},
title = {{Hard Problems on Random Graphs}},
booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
pages = {40:140:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771382},
ISSN = {18688969},
year = {2020},
volume = {168},
editor = {Artur Czumaj and Anuj Dawar and Emanuela Merelli},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12447},
URN = {urn:nbn:de:0030drops124477},
doi = {10.4230/LIPIcs.ICALP.2020.40},
annote = {Keywords: random graphs, averagecase complexity, firstorder model checking}
}
29.06.2020
Keywords: 

random graphs, averagecase complexity, firstorder model checking 
Seminar: 

47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Issue date: 

2020 
Date of publication: 

29.06.2020 