pith. sign in

arxiv: 2409.14783 · v3 · submitted 2024-09-23 · 💻 cs.CC

Disjoint covering of bipartite graphs with s-clubs

Angelo Monti , Blerina Sinaimeri This is my paper

Pith reviewed 2026-05-23 20:49 UTC · model grok-4.3

classification 💻 cs.CC
keywords s-clubsbipartite graphsNP-completenessgraph partitioningdisjoint coveringapproximation hardness
0
0 comments X

The pith

Partitioning bipartite graphs into a fixed number of s-clubs is NP-complete for fixed k at least 2 and most fixed s.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that deciding whether the vertices of a bipartite graph can be partitioned into at most k disjoint s-clubs is NP-complete when both k and s are fixed constants, for any k greater than or equal to 2 and for odd s at least 3 or even s at least 8. This result strengthens earlier hardness proofs by fixing both parameters rather than allowing them to vary with the input. The authors also prove that maximizing the number of vertices covered by vertex-disjoint large s-clubs is NP-hard to approximate within a factor of 95/94 in bipartite graphs for certain fixed t and s values. Finally they give a polynomial-time algorithm for the special case of (2,2)-MAX-DCC that resolves a prior open question.

Core claim

The (k,s)-PC problem, which asks whether the vertices of a graph can be partitioned into at most k disjoint s-clubs, remains NP-complete even when restricted to bipartite graphs, for every fixed k greater than or equal to 2 and every fixed odd s greater than or equal to 3 or even s greater than or equal to 8. The same class of graphs yields NP-hardness of approximation within 95/94 for the maximum disjoint (t,s)-club covering problem when t is fixed at least 8 for s=3 and at least 5 for s=2. A polynomial-time algorithm exists for the special case (2,2)-MAX-DCC.

What carries the argument

Polynomial-time reductions that map instances of known NP-complete problems to bipartite graphs while keeping both k and s fixed and preserving yes/no answers.

If this is right

  • No polynomial-time algorithm exists for (k,s)-PC on bipartite graphs unless P equals NP, for the stated fixed parameters.
  • The same hardness applies to the approximation version of maximum disjoint s-club covering for the listed fixed t and s.
  • The special case of covering with 2-clubs of size at least 2 admits an efficient exact solution on general graphs.
  • Hardness holds even though the input graphs are bipartite and therefore free of odd cycles.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar reductions may establish hardness for s-club problems on other restricted graph families such as planar or bounded-degree graphs.
  • The polynomial algorithm for the smallest parameters could serve as a building block for branch-and-bound methods on slightly larger fixed s.
  • The results indicate that network partitioning tasks modeled with s-clubs will remain intractable on bipartite input structures for most constant s.

Load-bearing premise

The constructed reductions always produce bipartite graphs while preserving the exact fixed values of k and s along with the yes/no answer.

What would settle it

A polynomial-time algorithm that correctly solves (k,s)-PC on arbitrary bipartite graphs for k=2 and s=3 would show the claimed NP-completeness does not hold.

Figures

Figures reproduced from arXiv: 2409.14783 by Angelo Monti, Blerina Sinaimeri.

Figure 1
Figure 1. Figure 1: (a) A bipartite graph G with the list coloring L : V (G) → [3] and (b) the corresponding graph G′ for s = 6 and k = 5. The gray vertices represent the auxiliary vertices added in the construction. In other words, for 1 ≤ i ≤ k, the set S ′ i consists of the vertices colored with i, along with the corresponding three color vertices, as well as the auxiliary vertices on the coloring paths and the compatibili… view at source ↗
Figure 2
Figure 2. Figure 2: The graph GM,8,3 obtained when the instance of Max-2B3DM problem is the set M = {(x1, y1, z1), (x2, y1, z1) (x1, y2, z2)}. Claim 2. The graph GM,t,3 can be constructed in polynomial time, is bipartite and has maximum degree t − 4. Proof. It is easy to see that GM,t,3 can be constructed in polynomial time. Then by construction V1 and V2 form a bipartition as there are no edges within the sets V1 and V2. Fur… view at source ↗
Figure 3
Figure 3. Figure 3: The graph GM,5,2 obtained when the instance of Max-2B3DM problem is the set M = {(x1, y1, z1), (x2, y1, z1) (x1, y2, z2)}. Claim 3. The graph GM,t,2 can be constructed in polynomial time, is bipartite and has maximum degree t − 1. Proof. It is easy to see that GM,t,2 can be constructed in polynomial time. Then by construction V1 and V2 form a bipartition as there are no edges within the sets V1 and V2. Fur… view at source ↗
read the original abstract

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 consider the $(k,s)$-PC problem where ask whether the vertices of $G$ can be partitioned into at most $k$ disjoint $s$-clubs. We prove that for any fixed $k \geq 2$ and for any fixed odd $s \geq 3$ or even $s\geq 8$, the $(k,s)$-PC problem 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 ($(t,s)$-MAX-DCC), 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 $(t,3)$-MAX-DCC for any fixed $t\geq 8$ and for $(t,2)$-MAX-DCC for any fixed $t\geq 5$ even for bipartite graphs. Previously, results were known only for $(3,2)$-MAX-DCC. Finally, we provide a polynomial-time algorithm for $(2,2)$-MAX-DCC resolving an open problem from Dondi \textit{et al.} (2019).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript proves NP-completeness of the (k,s)-PC problem (deciding whether the vertices of a graph can be partitioned into at most k s-clubs) for every fixed k ≥ 2 and every fixed odd s ≥ 3 or even s ≥ 8, even when the input is restricted to bipartite graphs; this strengthens the 1999 result of Abbas-Stewart by keeping both parameters constant rather than part of the input. It additionally establishes that (t,s)-MAX-DCC is NP-hard to approximate within 95/94 for (t,3)-MAX-DCC with any fixed t ≥ 8 and for (t,2)-MAX-DCC with any fixed t ≥ 5 on bipartite graphs, and supplies a polynomial-time algorithm for the special case (2,2)-MAX-DCC that resolves an open question of Dondi et al. (2019).

Significance. If the reductions are correct, the fixed-parameter NP-completeness results tighten the complexity classification of s-club partitioning on bipartite graphs and credit is due for the explicit strengthening over prior work. The inapproximability thresholds for the maximum disjoint covering problem extend existing hardness results to additional constant (t,s) pairs on bipartite inputs. The polynomial algorithm for (2,2)-MAX-DCC directly addresses a stated open problem.

minor comments (2)
  1. The abstract states the ranges for s but the introduction or §2 should explicitly recall why even s between 4 and 6 are excluded (diameter parity in bipartite graphs) to make the case distinction self-contained.
  2. Notation for (t,s)-clubs is introduced in the abstract and §1; a single consolidated definition paragraph in §2 would improve readability before the hardness proofs.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript, the assessment of its significance, and the recommendation of minor revision. No major comments were listed in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central results are NP-completeness proofs for (k,s)-PC on bipartite graphs (fixed k≥2, s in specified ranges) and approximation hardness plus a polynomial algorithm for variants of (t,s)-MAX-DCC. These rest on explicit constructions of polynomial-time reductions from established NP-complete problems (e.g., standard graph problems) that preserve the fixed parameters and yes/no answers, plus a direct algorithm for the (2,2) case. No equations, parameters, or claims reduce to self-definition, fitted inputs renamed as predictions, or load-bearing self-citations; the derivations are self-contained standard complexity arguments independent of the paper's own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard definitions of graphs, diameter, NP-completeness, and polynomial-time reductions; no free parameters, invented entities, or ad-hoc axioms are introduced.

axioms (1)
  • standard math Standard definitions of undirected graphs, diameter, s-clubs, and NP-completeness via Karp reductions
    Invoked throughout the abstract when stating the decision and optimization problems.

pith-pipeline@v0.9.0 · 5876 in / 1389 out tokens · 28760 ms · 2026-05-23T20:49:43.383598+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Discrete Applied Mathematics 91(1–3), 1–23 (Jan 1999)

    Abbas, N., Stewart, L.: Clustering bipartite and chordal graphs: Complexity, sequen- tial and parallel algorithms. Discrete Applied Mathematics 91(1–3), 1–23 (Jan 1999). https://doi.org/10.1016/s0166-218x(98)00094-8

    work page doi:10.1016/s0166-218x(98)00094-8 1999

  2. [2]

    Cam- bridge University Press (Jul 1998)

    Asratian, A.S., Denley, T.M.J., H¨ aggkvist, R.: Bipartite Graphs and their Applications. Cam- bridge University Press (Jul 1998). https://doi.org/10.1017/cbo9780511984068, http://dx.doi. org/10.1017/CBO9780511984068

    work page doi:10.1017/cbo9780511984068 1998

  3. [3]

    In: 2014 International Computer Science and Engineering Conference (ICSEC)

    Chang, J.M., Yang, J.S., Peng, S.L.: On the complexity of graph clustering with bounded diam- eter. In: 2014 International Computer Science and Engineering Conference (ICSEC). vol. 10, p. 18–22. IEEE (Jul 2014). https://doi.org/10.1109/icsec.2014.6978122

    work page doi:10.1109/icsec.2014.6978122 2014

  4. [4]

    In: Italian Conference on Algorithms and Complexity

    Chleb´ ık, M., Chleb´ ıkov´ a, J.: Approximation hardness for small occurrence instances of np-hard problems. In: Italian Conference on Algorithms and Complexity. pp. 152–164. Springer (2003)

    work page 2003

  5. [5]

    Theoretical Computer Science 354(3), 320–338 (2006)

    Chleb´ ık, M., Chleb´ ıkov´ a, J.: Complexity of approximating bounded variants of optimization problems. Theoretical Computer Science 354(3), 320–338 (2006). https://doi.org/https://doi.org/10.1016/j.tcs.2005.11.029, foundations of Computation The- ory (FCT 2003)

    work page doi:10.1016/j.tcs.2005.11.029 2006

  6. [6]

    The MIT Press, 2nd edn

    Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. The MIT Press, 2nd edn. (2001), http://www.amazon.com/ Introduction-Algorithms-Thomas-H-Cormen/dp/0262032937%3FSubscriptionId% 3D13CT5CVB80YFWJEPWS02%26tag%3Dws%26linkCode%3Dxm2%26camp%3D2025%26creative% 3D165953%26creativeASIN%3D0262032937

    work page arXiv 2001

  7. [7]

    Information Processing Letters 61(3), 121–127 (Feb 1997)

    Deogun, J.S., Kratsch, D., Steiner, G.: An approximation algorithm for clustering graphs with dominating diametral path. Information Processing Letters 61(3), 121–127 (Feb 1997). https://doi.org/10.1016/s0020-0190(97)81663-8

    work page doi:10.1016/s0020-0190(97)81663-8 1997

  8. [8]

    Algorithmica 85(4), 992–1028 (2023)

    Dondi, R., Lafond, M.: On the tractability of covering a graph with 2-clubs. Algorithmica 85(4), 992–1028 (2023). https://doi.org/10.1007/S00453-022-01062-3

    work page doi:10.1007/s00453-022-01062-3 2023

  9. [9]

    Theoretical Computer Science 777, 243–251 (Jul 2019)

    Dondi, R., Mauri, G., Zoppis, I.: On the tractability of finding disjoint clubs in a network. Theoretical Computer Science 777, 243–251 (Jul 2019). https://doi.org/10.1016/j.tcs.2019.03.045

    work page doi:10.1016/j.tcs.2019.03.045 2019

  10. [10]

    Theoretical Computer Science 410(21–23), 2045–2053 (May 2009)

    Fleischner, H., Mujuni, E., Paulusma, D., Szeider, S.: Covering graphs with few com- plete bipartite subgraphs. Theoretical Computer Science 410(21–23), 2045–2053 (May 2009). https://doi.org/10.1016/j.tcs.2008.12.059

    work page doi:10.1016/j.tcs.2008.12.059 2045

  11. [11]

    Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP- Completeness. W. H. Freeman (1979)

    work page 1979

  12. [12]

    Discrete Applied Mathematics 117(1–3), 65–79 (Mar 2002)

    Gravier, S., Kobler, D., Kubiak, W.: Complexity of list coloring problems with a fixed total number of colors. Discrete Applied Mathematics 117(1–3), 65–79 (Mar 2002). https://doi.org/10.1016/s0166-218x(01)00179-2

    work page doi:10.1016/s0166-218x(01)00179-2 2002

  13. [13]

    Algorithms 9(1), 21 (Mar 2016)

    Komusiewicz, C.: Multivariate algorithmics for finding cohesive subnetworks. Algorithms 9(1), 21 (Mar 2016). https://doi.org/10.3390/a9010021, http://dx.doi.org/10.3390/a9010021

    work page doi:10.3390/a9010021 2016

  14. [14]

    Social Network Analysis and Mining 6(1) (Apr 2016)

    Laan, S., Marx, M., Mokken, R.J.: Close communities in social networks: boroughs and 2-clubs. Social Network Analysis and Mining 6(1) (Apr 2016). https://doi.org/10.1007/s13278-016-0326-0

    work page doi:10.1007/s13278-016-0326-0 2016

  15. [15]

    Quality and Quantity 13(2), 161–173 (Apr 1979)

    Mokken, R.J.: Cliques, clubs and clans. Quality and Quantity 13(2), 161–173 (Apr 1979). https://doi.org/10.1007/bf00139635, http://dx.doi.org/10.1007/BF00139635

    work page doi:10.1007/bf00139635 1979

  16. [16]

    Social Network Analysis and Mining 6(1) (Jun 2016)

    Mokken, R.J., Heemskerk, E.M., Laan, S.: Close communication and 2-clubs in cor- porate networks: Europe 2010. Social Network Analysis and Mining 6(1) (Jun 2016). https://doi.org/10.1007/s13278-016-0345-x, http://dx.doi.org/10.1007/s13278-016-0345-x

    work page doi:10.1007/s13278-016-0345-x 2010

  17. [17]

    Cambridge university press (2011) 12

    Williamson, D.P., Shmoys, D.B.: The design of approximation algorithms. Cambridge university press (2011) 12

    work page 2011

  18. [18]

    In: Proceedings of the 11th International Joint Conference on Biomedical Engineering Systems and Technologies

    Zoppis, I., Dondi, R., Santoro, E., Castelnuovo, G., Sicurello, F., Mauri, G.: Optimizing social interaction. In: Proceedings of the 11th International Joint Conference on Biomedical Engineering Systems and Technologies. p. 651–657. SCITEPRESS - Science and Technology Publications (2018). https://doi.org/10.5220/0006730606510657, http://dx.doi.org/10.5220...

    work page doi:10.5220/0006730606510657 2018