License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.47
URN: urn:nbn:de:0030-drops-187000
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18700/
Figiel, Aleksander ;
Koana, Tomohiro ;
Nichterlein, André ;
Wünsche, Niklas
Correlating Theory and Practice in Finding Clubs and Plexes
Abstract
For solving NP-hard problems there is often a huge gap between theoretical guarantees and observed running times on real-world instances. As a first step towards tackling this issue, we propose an approach to quantify the correlation between theoretical and observed running times.
We use two NP-hard problems related to finding large "cliquish" subgraphs in a given graph as demonstration of this measure. More precisely, we focus on finding maximum s-clubs and s-plexes, i. e., graphs of diameter s and graphs where each vertex is adjacent to all but s vertices. Preprocessing based on Turing kernelization is a standard tool to tackle these problems, especially on sparse graphs. We provide a parameterized analysis for the Turing kernelization and demonstrate their usefulness in practice. Moreover, we demonstrate that our measure indeed captures the correlation between these new theoretical and the observed running times.
BibTeX - Entry
@InProceedings{figiel_et_al:LIPIcs.ESA.2023.47,
author = {Figiel, Aleksander and Koana, Tomohiro and Nichterlein, Andr\'{e} and W\"{u}nsche, Niklas},
title = {{Correlating Theory and Practice in Finding Clubs and Plexes}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {47:1--47:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-295-2},
ISSN = {1868-8969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18700},
URN = {urn:nbn:de:0030-drops-187000},
doi = {10.4230/LIPIcs.ESA.2023.47},
annote = {Keywords: Preprocessing, Turing kernelization, Pearson correlation coefficient}
}
