Cycle convexity problems hard for graphs with limited degree
Computing the Helly Number, Radon Number and Rank in Cycle Convexity
Discrete Mathematics
Summary
The paper looks at three numbers that describe how certain cycles in a graph relate to each other, called the Helly number, Radon number, and rank. It shows that figuring out whether these numbers reach a certain size is computationally very hard, even for simple-looking graphs with limited connections. The authors also describe exactly which special graphs make these numbers very large. This helps understand both the complexity and the structure behind these graph parameters.
What this means in practice
- •For graph algorithm designers: Avoid relying on efficient exact computation of Helly number, Radon number, or rank in cycle convexity due to proven hardness results.
- •For network modelers: Use structural characterizations of graphs with extremal Helly, Radon, or rank values to identify or rule out complex cycle dependencies in network topology analysis.
A theory result. No direct application yet.
Authors
Revathy S. Nair, Bijo S. Anand, Ullas Chandran S. V., Julliano R. Nascimento, Arun Anil
Abstract
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$.