Covering a graph with cohesive subgraphs is a classical problem in theoretical computer science, for example when the cohesive subgraph model considered is a clique. In this paper, we consider as a model of cohesive subgraph the 2-clubs, which are induced subgraphs of diameter at most 2. We prove new complexity results on the Min 2-Club Cover problem, a variant recently introduced in the literature which asks to cover the vertices of a graph with a minimum number of 2-clubs. First, we answer an open question on the decision version of Min 2-Club Cover that asks if it is possible to cover a graph with at most two 2-clubs, and we prove that it is W[1]-hard when parameterized by the distance to a 2-club. Then, we consider the complexity of Min 2-Club Cover on some graph classes. We prove that Min 2-Club Cover remains NP-hard on subcubic planar graphs, W[2]-hard on bipartite graphs when parameterized by the number of 2-clubs in a solution, and fixed-parameter tractable on graphs having hounded treewidth.

(2023). On the Tractability of Covering a Graph with 2-Clubs [journal article - articolo]. In ALGORITHMICA. Retrieved from https://hdl.handle.net/10446/261618

On the Tractability of Covering a Graph with 2-Clubs

Dondi, Riccardo;
2023-01-01

Abstract

Covering a graph with cohesive subgraphs is a classical problem in theoretical computer science, for example when the cohesive subgraph model considered is a clique. In this paper, we consider as a model of cohesive subgraph the 2-clubs, which are induced subgraphs of diameter at most 2. We prove new complexity results on the Min 2-Club Cover problem, a variant recently introduced in the literature which asks to cover the vertices of a graph with a minimum number of 2-clubs. First, we answer an open question on the decision version of Min 2-Club Cover that asks if it is possible to cover a graph with at most two 2-clubs, and we prove that it is W[1]-hard when parameterized by the distance to a 2-club. Then, we consider the complexity of Min 2-Club Cover on some graph classes. We prove that Min 2-Club Cover remains NP-hard on subcubic planar graphs, W[2]-hard on bipartite graphs when parameterized by the number of 2-clubs in a solution, and fixed-parameter tractable on graphs having hounded treewidth.
articolo
2023
Dondi, Riccardo; Lafond, Manuel
(2023). On the Tractability of Covering a Graph with 2-Clubs [journal article - articolo]. In ALGORITHMICA. Retrieved from https://hdl.handle.net/10446/261618
File allegato/i alla scheda:
File Dimensione del file Formato  
algorithmica23.pdf

accesso aperto

Versione: publisher's version - versione editoriale
Licenza: Creative commons
Dimensione del file 741.71 kB
Formato Adobe PDF
741.71 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10446/261618
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 2
social impact