Disjoint Covering of Bipartite Graphs with s-clubs

For a positive integer s, an s-club in a graph G is a set of vertices inducing a subgraph with diameter at most s. As generalizations of cliques, s-clubs offer a flexible model for real-world networks. This paper addresses the problems of partitioning and disjoint covering of vertices with s-clubs on bipartite graphs. First we prove that for any fixed s≥3 and fixed k≥3, determining whether the vertices of G can be partitioned into at most k disjoint s-clubs is NP-complete even for bipartite graphs. Note that our NP-completeness result is stronger than the one in Abbas and Stewart (1999), as we assume that both s and k are constants and not part of the input. Additionally, we study the Maximum Disjoint (t, s)-Club Covering problem (MAX-DCC(t, s)), which aims to find a collection of vertex-disjoint (t, s)-clubs (i.e. s-clubs with at least t vertices) that covers the maximum number of vertices in G. We prove that it is NP-hard to achieve an approximation factor of 9594 for MAX-DCC(t, 3) for any fixed t≥8 and for MAX-DCC(t, 2) for any fixed t≥5 even for bipartite graphs. Previously, results were known only for MAX-DCC(3, 2). Finally, we provide a polynomial-time algorithm for MAX-DCC(2, 2) resolving an open problem from Dondi et al. (2019).