Computing the Helly Number, Radon Number and Rank in Cycle Convexity

• Cycle convexity was introduced by Araújo et al. and is motivated in part by graph theory and knot theory.Source: §1 · p. 2
• The paper studies the Helly number, Radon number, and rank under cycle convexity, including their threshold complexity and extremal graph classes.Source: §1 · p. 2
• All three parameters are NP-hard to compute by threshold decision, even on planar graphs of maximum degree at most 6.Source: §1 · p. 2
• The paper characterizes connected graphs in which these parameters attain n −1 and n −2.Source: §1 · p. 2

• The paper considers connected, simple, undirected graphs; a unicyclic graph is connected and has exactly one cycle.Source: §2 · p. 2
• A cycle interval adds vertices that form a cycle with vertices of the set; iterating this operation yields the cycle convex hull.Source: §2 · p. 3
• The Helly, Radon, and rank parameters are maximum sizes of sets satisfying their respective independence conditions.Source: §2 · p. 3
• For any of the three parameters π(G), 2 ≤ π(G) ≤ n(G), and π(G) ≥ α(G) when n(G) ≥ 3.Source: §2 · p. 3
• Each parameter equals n(G) exactly when G is a forest, and every set independent for any of the three notions induces a forest.Source: §2 · p. 3
• If every adjacent pair is a hull set, each parameter equals max{2, α(G)}.Source: §2 · p. 3

• The three threshold problems are NP-hard even on planar graphs of maximum degree at most 6, and their general-graph versions are NP-hard and W[1]-hard.Source: §3 · pp. 3–4
• The reduction replaces each edge of a planar maximum-degree-3 Independent Set instance with a five-vertex gadget, preserving planarity and producing maximum degree at most 6.Source: §3 · p. 4
• The reduction maps an Independent Set threshold k to k′ = k + 3m, with an independent set of size at least k exactly when the constructed graph has a corresponding parameter-independent set of size at least k′.Source: §3 · p. 4
• In the constructed graph, every subset of the selected witness set is convex, making it independent for each of the three parameters.Source: §3 · p. 4
• For each gadget, the selected vertices are bounded by two when both original edge endpoints are selected, and by three otherwise.Source: §3 · p. 5
• These gadget bounds yield |S| ≤ 3m + |SG| − |E(G[SG])|, which implies that a sufficiently large witness in the constructed graph gives an independent set of size at least k in the original graph.Source: §3 · p. 5
• On planar graphs, all three problems are fixed-parameter tractable when parameterized by solution size, despite remaining NP-hard at maximum degree 6.Source: §3 · p. 5
• The paper notes that rank’s known W[1]-hardness by solution size on general graphs does not extend to planar graphs unless FPT = W[1].Source: §3 · p. 5

4 Extremal values

• For either extremal value, the Helly number, Radon number, and rank coincide.The paper notes that the three parameters coincide at both n−1 and n−2.Source: §4 · p. 6
• All three parameters attain n on forests.This is the starting extremal characterization motivating the study of n−1 and n−2.Source: §4 · p. 6
• For connected graphs, each of the three parameters equals n−1 exactly when the graph is unicyclic.The rank argument shows that a graph with rank n−1 has exactly one cycle, and conversely a unique cycle yields rank n−1.Source: §4 · p. 6
• Theorem 3 characterizes the n−2 case through equivalent conditions for rank, Helly number, and Radon number.The proof analyzes maximum convexly independent or Helly-independent sets whose complements contain two vertices, with the induced subgraph on the remaining vertices forming a forest.Source: §4 · pp. 7–8
• In the n−2 analysis, the proofs identify bicyclic graphs and constructions involving two omitted vertices and forest components.When the induced forest has one component, the cases lead to bicyclic graphs or graphs in F2; with multiple components, the arguments also identify F3 cases.Source: §4 · pp. 7–8

• The three parameters coincide when they attain n−1 or n−2, and the paper characterizes the graphs attaining both values.Source: §5 · p. 9
• When rkcc(G) ≤ 3, hlcc(G), rdcc(G), and rkcc(G) are equal, but a figure gives hlcc(G) = rdcc(G) = 3 < 4 = rkcc(G).Source: §5 · p. 9
• Four is the smallest value at which the three parameters can differ, and the paper conjectures that hlcc(G) = rdcc(G) for every connected graph.Source: §5 · p. 9
• The threshold decision problems remain hard even for planar graphs of bounded maximum degree.Source: §5 · p. 9