2026-08-15T13:12:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25145 2025-12-15T07:48:49Z ddc:004 open_access

On Maximum 2-Clubs Dumont, Joanne Lampis, Michael Liedloff, Mathieu Perez, Anthony Todinca, Ioan 2-clubs chordal graphs SETH parameterized algorithms We consider the Maximum 2-Club problem where one is given as input an undirected graph G = (V,E) and seeks a subset of vertices S of maximum size such that any pair of vertices in S is connected by a path of length at most 2 in the graph induced by S. This problem is a natural relaxation of the famous Maximum Clique problem where any pair of vertices must be connected by an edge. Maximum 2-Club has been well-studied and is known to be NP-complete even on split graphs. It can be solved exactly in O^*(1.62ⁿ) time, where n denotes the number of vertices of the input graph, while being polynomial-time solvable on several graph classes. Parameterized algorithms for structural parameters have also been considered, leading in particular to an algorithm with a double-exponential dependence in the parameter treewidth. Such an algorithm is actually the best one known for the larger parameter vertex cover size up to a constant in the exponent. We provide new results in both directions. We first prove that the double-exponential dependence for parameter vertex cover size is unavoidable under the Exponential Time Hypothesis (ETH). This answers a question left open by Hartung, Komusiewicz, Nichterlein and Suchỳ [Hartung et al., 2015]. Our result also implies that the problem cannot be solved in time sub-exponential in n even for split graphs. We then provide an exact algorithm for the problem restricted to chordal graphs, running in O^*(1.1996ⁿ) time, by reducing Maximum 2-Club on this class to Maximum Independent Set on arbitrary graphs with the same number of vertices. The same reduction shows that we can enumerate all maximum (and inclusion-wise maximal) 2-clubs of a chordal graph in O^*(3^{n/3}) = O^*(1.4423ⁿ) time. We conclude by providing a construction of split graphs with Ω(3^{n/3}/poly(n)) maximum2-clubs, for some polynomial poly showing that the bound for enumeration is essentially tight. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joanne Dumont and Michael Lampis and Mathieu Liedloff and Anthony Perez and Ioan Todinca 2025 Is Part Of LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2025.13 urn:nbn:de:0030-drops-251454 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.13 eng https://creativecommons.org/licenses/by/4.0/legalcode