2022/09/08 by Michael McKay, McKay, Michael, David F. Manlove +1
Computer Science · Engineering · #Advanced Manufacturing and Logistics Optimization #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.2209.03684
openalex publication_date 2022/09/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of finding a maximum-cardinality set of r-cliques in an undirected graph of fixed maximum degree Δ, subject to the cliques in that set being either vertex-disjoint or edge-disjoint. It is known for r=3 that the vertex-disjoint (edge-disjoint) problem is solvable in linear time if Δ=3 (Δ=4) but APX-hard if Δ≥ 4 (Δ≥ 5). We generalise these results to an arbitrary but fixed r ≥ 3, and provide a complete complexity classification for both the vertex- and edge-disjoint variants in graphs of maximum degree Δ. Specifically, we show that the vertex-disjoint problem is solvable in linear time if Δ< 3r/2 - 1, solvable in polynomial time if Δ< 5r/3 - 1, and APX-hard if Δ≥ \lceil 5r/3 \rceil - 1. We also show that if r≥ 6 then the above implications also hold for the edge-disjoint problem. If r ≤ 5, then the edge-disjoint problem is solvable in linear time if Δ< 3r/2 - 1, solvable in polynomial time if Δ≤ 2r - 2, and APX-hard if Δ> 2r - 2.