2026-07-22T17:01:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18700 2024-03-06T11:02:30Z ddc:004 open_access

Correlating Theory and Practice in Finding Clubs and Plexes Figiel, Aleksander Koana, Tomohiro Nichterlein, André Wünsche, Niklas Preprocessing Turing kernelization Pearson correlation coefficient 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aleksander Figiel and Tomohiro Koana and André Nichterlein and Niklas Wünsche 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.47 urn:nbn:de:0030-drops-187000 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.47 eng https://creativecommons.org/licenses/by/4.0/legalcode