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 \ge 3\) and fixed \(k \ge 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 \(\frac{95}{94} \) for MAX-DCC(t, 3) for any fixed \(t\ge 8\) and for MAX-DCC(t, 2) for any fixed \(t\ge 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).

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Disjoint Covering of Bipartite Graphs with s-clubs

  • Angelo Monti,
  • Blerina Sinaimeri

摘要

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 \ge 3\) and fixed \(k \ge 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 \(\frac{95}{94} \) for MAX-DCC(t, 3) for any fixed \(t\ge 8\) and for MAX-DCC(t, 2) for any fixed \(t\ge 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).