On the parameterized complexity of non-hereditary relaxations of clique
Overview & Synopsis
We investigate the parameterized complexity of several problems formalizing cluster identification in graphs. In other words we ask whether a graph contains a large enough and sufficiently connected subgraph. We study here three relaxations of Clique: s-Club and s-Clique, in which the relaxation is focused on the distances in respectively the cluster and the original graph, and γ-Complete Subgraph in which the relaxation is made on the minimal degree in the cluster. As these three problems are known to be NP-hard, we study here their parameterized complexities. We prove that s-Club and s-Clique are NP-hard even restricted to graphs of degeneracy ≤ 3 whenever s ≥ 3, and to graphs of degeneracy ≤ 2 whenever s ≥ 5, which is a strictly stronger result than its W[1]-hardness parameterized by the degeneracy. We also obtain that these problems are solvable in polynomial time on graphs of degeneracy 1. Concerning γ-Complete Subgraph, we prove that it is W[1]-hard parameterized by both the degeneracy, which implies the W[1]-hardness parameterized by the number of vertices in the γ-complete-subgraph, and the number of elements outside the γ-complete subgraph.
hal.science)
← / → for pages • + / - for zoom • 0 to fit width
Powered by Mozilla PDF.js v3.11
Document Information
| Document Title | On the parameterized complexity of non-hereditary relaxations of clique |
|---|---|
| Author / Organization | Ambroise Baril, Antoine Castillon, Nacim Oijid |
| Subject & Discipline | Multidisciplinary Academic Open Research |
| Categories | Science & Mathematics |
| Publication Year | 2023 |
| License / Rights | Open Access / Creative Commons |
| Resource Verification | Listed PDF (Verification Pending) |
| Original Host Website |
HAL Open Science
(hal.science)
|
| File Format | application/pdf (Portable Document Format) |
| Language | EN |
| Catalog ID | DOC-177020 |
| Original Source Link | Visit Source Page on hal.science » |