γ-clustering problems: Classical and parametrized complexity
We introduce the γ-clustering problems, which are variants of the well-known Cluster Editing/Deletion/Completion problems, and defined as: given a graph G, how many edges must be edited in G, deleted from G, or added to G in order to have a disjoint union of γ-quasi-cliques. We provide here the complete complexity classification of these problems along with FPT algorithms parameterized by the number of modifications, for the NP-complete problems. We also study here a variant of these problems where the number of final clusters is a fixed constant, obtaining mostly the same results regarding classical and parameterized complexity.
Authors
- Hamida Seba (ORCID: https://orcid.org/0000-0003-0670-815X)
- Antoine Castillon
- Clarisse Dhaenens (ORCID: https://orcid.org/0000-0002-6590-7215)
- Julien Baste (ORCID: https://orcid.org/0000-0002-7869-0959)
- Mohammed Haddad (ORCID: https://orcid.org/0000-0002-8699-7520)
Institutions
- Université Claude Bernard Lyon 1 (FR)
- Centre National de la Recherche Scientifique (FR)
- Université de Lille (FR)
- Centre de Recherche en Informatique (FR)
- LabEx PERSYVAL-Lab (FR)
- Laboratoire d'Informatique en Images et Systèmes d'Information (FR)
- Institut National des Sciences Appliquées de Lyon (FR)
- École Centrale de Lille (FR)
Publication Details
- Journal
- Theoretical Computer Science
- Published
- 2024-08-22
- DOI
- https://doi.org/10.1016/j.tcs.2024.114784
- Primary Topic
- Complex Network Analysis Techniques
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Agence Nationale de la Recherche