Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
The authors investigate the computational complexity and extremal structures of three classical geometric invariants—the Helly number, Radon number, and rank—under graph cycle convexity. They prove that deciding whether any of these three parameters meets a threshold $k$ is both NP-hard and W[1]-hard parameterized by $k$, with NP-hardness persisting even when restricted to planar graphs of maximum degree six. Complementing these hardness results, the work establishes complete structural characterizations for connected graphs where these parameters achieve near-maximal extremal values of $n-1$ and $n-2$.
Cycle convexity invariants remain intractable even on degree-bounded planar topologies, proving that Helly, Radon, and rank computations cannot admit efficient fixed-parameter algorithms parameterized by their threshold values.
In this paper, we investigate three fundamental convexity parameters of graphs under cycle convexity, namely the Helly number, Radon number, and rank. We first study the computational complexity of these parameters. For each of these parameters, we consider the associated threshold decision problem of determining whether the parameter of a given graph is at least a prescribed integer. We establish that all three problems are $\NP$-hard and $\W[1]$-hard when parameterized by the threshold. Moreover, we strengthen these results by showing that the $\NP$-hardness persists even when the input is restricted to planar graphs of maximum degree at most $6$. We also focus on the structural properties of connected graphs corresponding to extremal values of these parameters. In particular, we characterize the graph classes for which the three parameters attain the values $n-1$ and $n-2$, where $n$ is the order of $G$.