# On the rank and the general position number in cycle convexity

Júlio Aráujo, Samuel N Aráujo, Pedro P Medeiros, Nicolas Nisse, Caroline Silva

► To cite this version:

Júlio Aráujo, Samuel N Aráujo, Pedro P Medeiros, Nicolas Nisse, Caroline Silva. On the rank and the general position number in cycle convexity. Inria & Université Cote d'Azur, CNRS, I3S, Sophia Antipolis, France. 2025. hal-05378038

HAL Id: hal-05378038

https://inria.hal.science/hal-05378038v1

Submitted on 22 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the rank and the general position number in cycle convexity

Júlio Aráujo<sup>a</sup>, Samuel N. Aráujo<sup>a,b,c,*</sup>, Pedro P. Medeiros<sup>b</sup>, Nicolas Nisse<sup>b</sup>, Caroline Silva<sup>b,d</sup>

<sup>a</sup>ParGO, Universidade Federal do Ceará, Fortaleza, Brazil

<sup>b</sup>Université Côte d'Azur, CNRS, Inria, I3S, Sophia Antipolis, France

<sup>c</sup>Instituto Federal de Educação Ciência e Tecnologia do Ceará, Crato, Brazil

<sup>d</sup>Universidade Estadual de Campinas, Campinas, Brazil

## Abstract

Graph convexities have been widely investigated through various combinatorial parameters that capture different aspects of convexity-related structures. The cycle convexity has been introduced due to its applications in the field of Knot Theory. In the cycle convexity, the interval $I(S)$ of a subset $S$ of vertices of a graph $G = (V, E)$ is the set of all vertices in $S$ union the vertices with two neighbors in a same connected component of $G[S]$. The hull of $S$ is the closure $H(S) = I^*(S)$, i.e., the set of vertices that can be obtained from $S$ by recursively adding to $S$ any vertex that is the neighbor of two vertices in a same connected component of $S$. In any graph convexity, it is classical to study the minimum size of a hull set of $G$, i.e., a minimum set such that $H(S) = V$. Previous works on other convexities also study the general position number of $G$, i.e., the maximum size of a set $S$ such that $v \notin I(S \setminus \{v\})$ for every $v \in S \subseteq V(G)$, and the rank of $G$, i.e., the maximum size of a set $S$ such that $v \notin H(S \setminus \{v\})$ for every $v \in S \subseteq V(G)$.

Here, we first show that the general position number of $G$ in the cycle convexity equals the maximum order of an induced forest in $G$. Then, we focus on the computational complexity of computing the rank of a given $G$ in the cycle convexity. We show that it is NP-hard, even if the input graph is known to be bipartite, and W[1]-hard parameterized by the size of the solution. Then, we prove that it is polynomial-time computable in various graph classes such as forests, cycles, complete graphs, complete bipartite graphs, cographs, Cartesian grids, chordal graphs, starlike graphs, and $(q, q-4)$-graphs. Surprisingly, the classes of Cartesian grids and of not 2-connected chordal graphs are quite involved. We conclude by showing fixed-parameter tractable algorithms for computing the rank of a given graph when parameterized by the neighborhood diversity, by vertex cover, or by the treewidth of the input graph.

**Keywords:** graph convexity, cycle convexity, rank, general position number

## 1. Introduction

We assume that the reader is familiar with the common terminology in Graph Theory and Complexity Theory [1, 2]. For a graph $G = (V, E)$, let $V(G) = V$, and $E(G) = E$. For any

<footnote>*Corresponding author</footnote>

<footnote>Email addresses: julio@mat.ufc.br (Júlio Aráujo), samuel.araujo@ifce.edu.br (Samuel N. Aráujo), pedropmed1@gmail.com (Pedro P. Medeiros), nicolas.nisse@inria.fr (Nicolas Nisse), caroline.silva@ic.unicamp.br (Caroline Silva)</footnote>
$S \subseteq V(G)$, let $G[S]$ be the subgraph of $G$ induced by the subset of vertices $S$. In this paper, we consider only simple, finite, and undirected graphs.

A convexity space, or simply convexity [3], is an ordered pair $(V, C)$ where $V$ is a set (in this paper, we only consider finite sets $V$) and $C$ is a subset family of $V$, called convex sets, such that $V, \emptyset \in C$ and that $C$ is closed under intersection. Let $(V, C)$ be a convex space, the convex hull of a set $S \subseteq V$, denoted by $H(S)$, is the inclusion-wise minimum convex set $C \in C$ such that $C \supseteq S$. If $H(S) = V$, we say that $S$ is a hull set of $(V, C)$.

When $V$ is the vertex set of a given graph $G$, we say that $(V, C)$ is a graph convexity. Most graph convexities are defined by an interval function $I: 2^V \to 2^V$, which satisfies: a) $S \subseteq I(S)$ (extensive law), b) $S \subseteq S'$ implies $I(S) \subseteq I(S')$ (monotone law) and c) $I(\emptyset) = \emptyset$ (normalization law) [4]. Therefore, in a convexity $(V, C)$ associated with the interval function $I$, a set $S$ is convex if and only if $I(S) = S$. Observe that from these properties, we can write $I^0(S) = S$ and $I^k(S) = I(I^{k-1}(S))$ for every $k \ge 1$. The convex hull of $S$ can be obtained as $H(S) = I^l(S)$ for some $l \ge 0$, where $I^k(S) = I^{k+1}(S)$ for all $k \ge l$. Under this notion, the convex hull of a subset $S$ is determined by repeatedly applying the interval function to $S$ until the resulting set stabilizes. In other words, for $k \ge 1$, as long as there exists a vertex $v \in I^k(S) \setminus I^{k-1}(S)$, we know that $I^{k-1}(S)$ is not yet convex. Therefore, we add $v$ to the convex hull of $S$ and say that the vertex $v$ is infected (or generated or contaminated) at step $k$.

Usually, in a graph convexity $(V, C)$ defined by an interval function $I$, the set $I(S)$ contains all vertices in $S$, as well as all vertices lying on paths between vertices in $S$ that satisfy some specific property. The most studied graph convexities are the geodesic convexity [5, 6], the $P_3$ convexity [7, 8], $P_3^*$ convexity [9], and the monophonic convexity [10, 11], where $I(S)$ contains, respectively, all vertices in every shortest path with endpoints in $S$, all vertices in every $P_3$ with endpoints in $S$, all vertices in every induced $P_3$ with endpoints in $S$ and all vertices in every induced path with endpoints in $S$.

Here, we are interested in cycle convexity, first introduced in [12]. The primary inspiration for the development of cycle convexity arose from its relevance in studying the tunnel number of knots and links in the field of Knot Theory [13]. In cycle convexity, the interval function is defined as

$$ 
\begin{aligned}
I(S) &= S \cup \{u \mid G[S \cup \{u\}]\} \text{ contains a cycle that contains } u \\
&= S \cup \{u \mid u \text{ has two neighbours in a same component of } G[S]\}.
\end{aligned}
$$

In [12], the interval number of a graph in the cycle convexity is investigated. The interval number of a graph $G$, denoted by $in(G)$, is the size of a smallest set $S$ of $G$, such that $I(S) = V(G)$. They showed that the problem to determine whether $in(G) \le k$ is NP-complete, even if $G$ is a split graph or a bounded-degree planar graph, and W[2]-hard even if $G$ is a bipartite graph when the problem is parameterized by $k$. On the other hand, they showed that the problem is polynomial-time solvable for outerplanar graphs, cobipartite graphs and interval graphs.

In [14], Araujo et al. examined the hull number in the cycle convexity. The hull number of a graph $G$, denoted by $hn(G)$, is the size of a smallest hull set $S$ of $G$. They showed that $hn(G) \le n/2$ when $G$ is a 4-regular planar graph on $n$ vertices. Furthermore, they proved that the problem to determine whether $hn(G) \le k$ for a given graph $G$ and a positive integer $k$ is NP-complete, even when $G$ is a planar graph, but the problem is solvable in polynomial time when $G$ is a chordal graph, $P_4$-sparse, or a grid.
In this paper, we are interested in the rank and general position numbers with respect to cycle convexity.

The general position number [15, 16] of a graph $G$ in any convexity with interval function $I$ is the maximum cardinality of a subset $S \subseteq V(G)$ such that for every $s \in S$, $s \notin I(S \setminus \{s\})$. We first show that, in the case of the cycle convexity, the general position number of a graph $G$, denoted by $gp(G)$, coincides with the forest number MIF($G$) of $G$ [17], the maximum number of vertices that induces a forest in $G$, as shown below.

**Proposition 1.** For every graph $G$, $gp(G) = \text{MIF}(G)$.

*Proof.* Let $S \subseteq V(G)$ such that $S$ is in general position, i.e., for every $s \in S$, $s \notin I(S \setminus \{s\})$. This implies that $s$ is not in any cycle in $G[S \cup \{s\}]$. Therefore, $S$ induces a forest in $G$. Conversely, if $G[S]$ is an induced forest, every subset of $S$ induces a forest. Hence for every $s \in S$, $s \notin S \setminus \{s\} = I(S \setminus \{s\})$. $\square$

An induced forest in a graph corresponds to the complement of a vertex set whose removal results in an acyclic graph. This set is often referred to as a *decycling set* or a *feedback vertex set*. Therefore, all known results about MIF($G$) and minimum feedback vertex set transfer to the general position in the cycle convexity. The maximum cardinality of an induced forest and minimum feedback vertex set in specific families of graphs have been well-studied in the literature; for instance: bipartite graphs [18], planar graphs [19, 20], hypercubes [21, 22], and distance regular graphs [23].

The general position number problem has its roots in the classical No-Three-in-Line problem [24], which asks for the maximum number of points that can be placed on an $n \times n$ grid such that no three lie on a common straight line. Despite decades of investigation, the exact value of this number remains unknown for $n > 46$ [25]. Inspired by this combinatorial question, Manuel and Klavžar [26] introduced the general position number as a graph parameter in geodesic convexity, and proved that its computation is NP-hard. More recently, Araújo et al. [27] showed that computing the general position number is also NP-hard in monophonic convexity, even when restricted to graphs of diameter two.

A closely related problem to the general position number is the rank of a graph, which is the main topic of our paper. Given a graph $G = (V, E)$, we say that $S \subseteq V$ is *convexly dependent* in $G$ if there exists $v \in S$ such that $v \in H(S \setminus \{v\})$. Otherwise, we say that $S$ is *convexly independent* in $G$. The *rank* of a graph $G$ [28, 29], denoted here by $rk(G)$ in the cycle convexity, is the largest cardinality of a convexly independent set in $G$. The notion of convex rank was first introduced by Jamison [28] in one of the first works on graph convexity. With respect to the monophonic and $P_3$ convexities, it was established in [29] that computing the rank is NP-hard. For the geodesic convexity, it was shown in [30] that the problem admits a polynomial-time algorithm when restricted to distance-hereditary graphs, but it remains NP-hard even when restricted to bipartite graphs, highlighting its computational intractability in general.

**Our contribution.** In this paper, we mainly focus on the computational complexity of the RANK Problem in cycle convexity, i.e., given a graph $G$ and an integer $k \in \mathbb{N}$, deciding if $rk(G) \le k$. In Section 2, we start with preliminary results showing that the rank can be trivially computed in forests, cycles, complete graphs, and complete bipartite graphs. Then, we characterize its behavior under union and join operations (Lemma 5). As straightforward consequences, we show that the rank of cographs can be computed in linear time (Corollary 6), but in the class of graphs obtained by joining two identical arbitrary graphs that the RANK Problem is NP-complete and $W[1]$-hard
(Corollary 7). We conclude this section with a more involved proof that the RANK Problem is NP-complete even in the class of bipartite graphs (Theorem 8).

The Section 3 is devoted to polynomial-time algorithms to solve the RANK Problem in several graph classes. In Section 3.1, we characterize the rank of any $n \times m$ Cartesian grid, depending on the parity of $n$ and $m$ (Theorem 14). In Section 3.2, we design a polynomial-time dynamic programming algorithm that computes the rank of chordal graphs (Theorem 17) generalizing some results in [31]. Then, we show that the rank can be computed in polynomial time in starlike graphs (Theorem 18 in Section 3.3) and in $(q, q-4)$-graphs (Theorem 22 in Section 3.4).

The Section 4 focuses on the parameterized complexity of the RANK Problem. We first show that the rank is FPT when parameterized by the neighborhood diversity of the input graph (Theorem 24) and so by the vertex cover of the input graph. Finally, by expressing the problem as a logic formula and as a consequence of Courcelle's Theorem, we show that the problem is also FPT when parameterized by the treewidth of the input graph plus the size of the solution (Theorem 25).

We conclude in Section 5 with several open questions.

## 2. Preliminaries and hardness results

In this section, we start with some basic results on the rank of a graph in cycle convexity. We then provide exact values of this parameter in basic graph classes. Finally, we discuss its complexity in general graphs.

Let us start with some basic observations that will be useful throughout the paper.

**Observation 2.** Let $G$ be a graph and $S \subseteq V(G)$. Note that if $u \in I(S) \setminus S$, then there is an induced cycle in $G[S \cup \{u\}]$ that contains $u$. Consequently, we can consider, if convenient, that the computation of $H_G(S)$ is made by only using induced cycles.

**Claim 1.** Let $S$ be a convexly independent set in any graph $G$ and let $S' \subseteq S$, then $S'$ is convexly independent.

*Proof.* For the purpose of contradiction, let us assume that $S'$ is not convexly independent in $G'$. Therefore, there exists $v \in S'$ such that $v \in H(S' \setminus \{v\})$. Consequently, $v \in H(S \setminus \{v\})$ (since if $X \subseteq Y$, $H(X) \subseteq H(Y)$), contradicting that $S$ is convexly independent. $\square$

**Claim 2.** Let $G$ be a graph. If $S \subseteq V$ is a convexly independent set in $G$, then $G[S]$ induces a forest (i.e., $G[S]$ is acyclic).

*Proof.* Assume, by contradiction, that $G[S]$ contains an induced cycle $C$. Note that for every $v \in V(C)$, we have $v \in H(S \setminus \{v\})$, a contradiction. $\square$

We denote by $\alpha(G)$ the largest size of a stable set of $G$ and by MIF($G$) the maximum size of a subset of vertices of $G$ that induces a forest [28].

**Lemma 3.** For every graph $G$, $\alpha(G) \le \text{rk}(G) \le \text{MIF}(G)$. Furthermore, the difference may be arbitrarily large.

*Proof.* Note that for every independent set $S$, $H(S) = S$. In particular, for every $v \in S$, we have $H(S \setminus \{v\}) = S \setminus \{v\}$. This implies that $S$ is convexly independent. Hence $\alpha(G) \le \text{rk}(G)$. The Claim 2 immediately implies $\text{rk}(G) \le \text{MIF}(G)$.
It should be noted that there are classes of graphs in which these parameters differ. For example, in a cycle with $n$ vertices, denoted by $C_n$, observe that $\alpha(C_n) = \lfloor \frac{n}{2} \rfloor$, while $\mathrm{rk}(C_n) = \mathrm{MIF}(C_n) = n - 1$.

Consider now the wheel graph $W_n$, where $V(W_n) = \{v_1, \dots, v_n\} \cup \{u\}$ for $n \ge 3$, the vertices $v_1, \dots, v_n$ induce a cycle and $u$ is a universal vertex. One can verify that $\mathrm{rk}(W_n) = \alpha(C_n) = \lfloor \frac{n}{2} \rfloor$, but $\mathrm{MIF}(W_n) = n - 1$. $\square$

The next straightforward theorem gives the general position and rank of several graph classes.

**Theorem 4.** Let $n, m \in \mathbb{N}^*$. Let $F_n$ (resp., $C_n$, resp., $K_n$) denote any forest (resp., cycle, resp., complete graph) with $n$ vertices, and let $K_{n,m}$ be the complete bipartite graph:

(a) $\mathrm{gp}(F_n) = \mathrm{rk}(F_n) = n;$

(b) $\mathrm{gp}(C_n) = \mathrm{rk}(C_n) = n - 1$, for any $n \ge 3$;

(c) $\mathrm{gp}(K_n) = \mathrm{rk}(K_n) = 2$, for any $n \ge 3$;

(d) $\mathrm{gp}(K_{n,m}) = \mathrm{rk}(K_{n,m}) + 1 = \max\{n, m\} + 1$, for any $n, m > 2$.

*Proof.* The first three items are trivial. The fourth one comes from the easy facts that, in $K_{n,m}$, any set $S$ containing at least one vertex in one part and at least two in the other part is a hull set for the cycle convexity, i.e., $H(S) = V(K_{n,m})$, and moreover, for any set $S$ containing vertices of a single part, then $H(S) = S$. Finally, if a set $S$ contains at least two vertices in each part, then $H(S) = I(S) = V(K_{n,m})$. $\square$

Given two disjoint graphs $G_1$ and $G_2$, the union of $G_1$ and $G_2$ is the graph $G_1 \cup G_2 = (V(G_1) \cup V(G_2), E(G_1) \cup E(G_2))$. The join of $G_1$ and $G_2$, denoted by $G_1 \oplus G_2$, is the graph obtained from $G_1 \cup G_2$ by adding every possible edge having one endpoint in $V(G_1)$ and the other in $V(G_2)$.

**Lemma 5.** Let $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ be two disjoint graphs. Then $\mathrm{rk}(G_1 \cup G_2) = \mathrm{rk}(G_1) + \mathrm{rk}(G_2)$ and

1. $\mathrm{rk}(G_1 \oplus G_2) = 2$ if $G_1 \oplus G_2$ is a complete graph, else

2. $\mathrm{rk}(G_1 \oplus G_2) = 3$ if $G_1$ is the disjoint union of 2 vertices and $G_2$ is the disjoint union of one vertex and one complete graph, else

3. $\mathrm{rk}(G_1 \oplus G_2) = \max\{\alpha(G_2); t + 1\}$, if $G_1$ is a one single vertex and $G_2$ has $t \ge 1$ connected components. In particular, $\mathrm{rk}(G_1 \oplus G_2) = \alpha(G_2) + 1$ if $G_2$ is the disjoint union of cliques and $\mathrm{rk}(G_1 \oplus G_2) = \alpha(G_2) = \max\{\alpha(G_1), \alpha(G_2)\}$ otherwise. Else,

4. $\mathrm{rk}(G_1 \oplus G_2) = \max\{\alpha(G_1), \alpha(G_2)\}$.

*Proof.* The fact that $\mathrm{rk}(G_1 \cup G_2) = \mathrm{rk}(G_1) + \mathrm{rk}(G_2)$ is trivial.

Let $G = G_1 \oplus G_2$. Then, the case when $G$ is a complete graph follows from Theorem 4. If $G_1$ is the disjoint union of two vertices $\{u, v\}$ and $G_2$ is the disjoint union of a vertex $\{w\}$ and a complete graph $K$ (possibly with one vertex), let us denote $G_1 \oplus G_2$ by $C_4^*$. One may check that $\{u, v, w\}$ is a maximum convexly independent set.

Let $G_1 = \{u\}$ and let $G_2 = H_1 \cup H_2 \cup \dots \cup H_t$, for $t \ge 1$, where the $H_i$'s are the connected components of $G_2$. Let $S \subseteq V(G_2) \setminus V(H_i)$, for some $1 \le i \le t$. Thus, $H(S \cup \{u\}) \cap H_i = \emptyset$. Moreover, for every $v_i \in H_i$, $H(S \cup \{u, v_i\}) \setminus V(H_i) \subseteq H(S \cup \{u\})$. Therefore, every maximal
convexly independent set of $G_1 \oplus G_2$ must contain some vertex $v_i \in V(H_i)$ for every $1 \le i \le t$. Now, let $S$ be any set such that $|H_i \cap S| = 1$ and $u \in H(S)$. Then, $V(H_i) \subseteq H(S)$. So, given a maximal convexly independent set $S$, if $u$ belongs to $S$ or is generated by $S \cap V(H_i)$ (for some $i \le t$ such that two adjacent vertices of $H_i$ are in $S$), then $|S \cap V(H_j)| = 1$ for every $1 \le i \ne j \le t$. Hence, the result follows, i.e., any maximal convexly independent set either is a stable set of $G_2$ or contains $u$ and exactly one vertex per component of $G_2$.

Let us assume that $G \ne C_4^*$, that $G$ is not a complete graph, and that $|V(G_1)| > 1$ and $|V(G_2)| > 1$. Thus, $G_1$ or $G_2$ is not a complete graph, and $\max\{\alpha(G_1), \alpha(G_2)\} > 1$.

By Lemma 3, $rk(G) \ge \alpha(G) = \max\{\alpha(G_1), \alpha(G_2)\} \ge 2$.

For the purpose of contradiction, let $S$ be a largest convexly independent set with size $|S| > \max\{\alpha(G_1), \alpha(G_2)\} \ge 2$. Hence, $S$ is not a stable set of $G$ (since a stable set of $G$ is either a stable set of $G_1$ or of $G_2$). Hence, there are $u, v \in S$ such that $\{u, v\} \in E(G)$.

First, assume that $\{u, v\} \in E(G_i)$ for $i \in \{1, 2\}$. Because $|V(G_{3-i})| \ge 2$, $\{u, v\}$ is a hull set ($H(\{u, v\}) = V(G)$). Therefore, since $S$ is a convexly independent set, then $S = \{u, v\}$, a contradiction.

Hence, $S$ must contain a vertex $u$ of $G_1$ and a vertex $v$ of $G_2$. If $S = \{u, v\}$, then $|S| = 2 \ge \max\{\alpha(G_1), \alpha(G_2)\} \ge 2$ and the result holds. Otherwise, $\{u, v, w\} \subseteq S$ with (w.l.o.g.) $u$ and $w$ not adjacent in $G_1$ (possible since either $G_1$ or $G_2$, say $G_1$, is not a complete graph) and $v$ in $G_2$. Note that $H(\{u, v, w\}) = V(G)$ and so $S = \{u, v, w\}$ (since $S$ is convexly independent). If $\max\{\alpha(G_1), \alpha(G_2)\} \ge 3$, the result holds.

Hence, let us assume that $\max\{\alpha(G_1), \alpha(G_2)\} \le 2$. Since $G \ne C_4^*$, either (u or w has a neighbor in $G_1$ (w.l.o.g., say u)) or v has a neighbor in $G_2$ or ($G_1$ consists of the disjoint union of u and w, and $G_2$ is the disjoint union of v and a complete graph of order at least 2) and, in all cases, $H(\{u, v\}) = V(G)$ contradicting that $S$ is convexly independent. □

Recall that a cograph is any graph without $P_4$ (path on 4 vertices) as an induced subgraph. It is well known [32] that the class of cographs can be defined recursively: one vertex is a cograph, the disjoint union of two cographs is a cograph and the join of two cographs is a cograph. Moreover, such a decomposition can be computed in linear time [33]. It follows:

**Corollary 6.** The rank of a cograph can be computed in linear time.

The INDEPENDENT SET Problem consists of computing a largest set of pairwise non-adjacent vertices in a graph $G$. It is well known that the INDEPENDENT SET Problem is NP-complete and W[1]-hard when parameterized by the size of the solution [2]. Given a graph $G$ and a positive integer $k$, define the decision problem RANK as determining whether $rk(G) \ge k$.

**Corollary 7.** The RANK problem is NP-complete and W[1]-hard when parameterized by $k$, even if $G$ belongs to the class of graphs obtained as the join of two copies of the same graph.

*Proof.* The problem is clearly in NP. Let $(G, k)$ be an instance of the INDEPENDENT SET with $\alpha(G) \ge 3$. Let $G' = (G \oplus G)$. By Lemma 5, then $rk(G') = \alpha(G)$ and so the result follows. □

One could also notice that Corollary 7 could also be proven by just adding a universal vertex to a connected non-complete graph $G$. In this case, again $\alpha(G) = rk(G)$ and the NP-hardness and W[1]-hardness follow.

To conclude this section, let us show that deciding whether $rk(G) \ge k$ is NP-complete, even if we know that the input graph $G$ is bipartite. Our reduction is from the SET PACKING problem.
The SET PACKING Problem has as input a triple $(U, \mathcal{S}, k)$ being $U$ an arbitrary ground set, $\mathcal{S}$ a family of subsets of $U$, and $k$ a positive integer, and aims at deciding whether there are at least $k$ pairwise disjoint sets of $\mathcal{S}$. This is a well-known NP-complete problem [34].

**Theorem 8.** The RANK problem is NP-complete, even if the input graph $G$ belongs to the class of bipartite graphs.

*Proof.* The problem is clearly in NP. Let $\mathcal{I} = (U, \mathcal{S}, k)$ be an instance of the SET PACKING Problem with $U = \{u_1, \cdots, u_n\}$ and $\mathcal{S} = \{S_1, \cdots, S_m\}$. W.l.o.g., we may assume that $n \ge 2$, $k \ge 3$ and, for every integer $1 \le i \le m$, there exists an integer $1 \le j \le m$ such that $j \ne i$ and $S_i \cap S_j \ne \emptyset$. We build an equivalent instance $(G(\mathcal{I}), k')$ for the RANK problem as follows.

For every $1 \le i \le m$, let $I_i = \{j \mid 1 \le j \le m, i \ne j, S_i \cap S_j \ne \emptyset\}$ be the set of indices of subsets in $\mathcal{S}$ that intersect with $S_i$ and let $I = \cup_{1 \le i \le m} \{\{i, j\} \mid j \in I_i\}$ be the family composed of pairs of intersecting sets of $\mathcal{S}$.

To build $G(\mathcal{I})$ (see Fig. 1), start with three pairwise disjoint stable sets: $R$ having cardinality $|R| = 2|I| + n + m$, $U' = \{u'_1, \cdots, u'_n\}$ and $S' = \{s'_1, \cdots, s'_m\}$. Then, add a join between $R$ and $U'$, i.e., add an edge between every $r \in R$ and every $u'_i \in U'$. Then, for every $1 \le i \le n$ and every $1 \le j \le m$, add the edge $\{u'_i, s'_j\}$ if and only if $u_i \in S_j$.

Then, for every $1 \le i < j \le m$, such that $S_i \cap S_j \ne \emptyset$, add two disjoint paths $P^{ij} = (a^{ij}, b^{ij}, c^{ij})$ and $P^{ji} = (a^{ji}, b^{ji}, c^{ji})$ and the edges $\{\{s'_i, a^{ij}\}, \{s'_i, c^{ij}\}, \{s'_i, a^{ji}\}, \{s'_j, a^{ji}\}, \{s'_j, c^{ji}\}, \{s'_j, a^{ij}\}\}$.

<figure><img src="image_2.png" /><figcaption>Figure 1: Representation of the reduction for the RANK problem in bipartite graphs. In this illustration, the corresponding instance of the set packing problem is such that $u_r \in S_i \cap S_j$ and $u_l \in S_j \cap S_k$. If $S_i$ and $S_k$ are part of a solution to SET PACKING, we depict in gray the corresponding selected vertices used to form a convexly independent set.</figcaption></figure>

For every $1 \le i \le m$, let $A^i = \{a^{ij} \mid j \in I_i\}$ and define $B^i$ and $C^i$ analogously. Note that $\{A^i, B^i, C^i\}$ is a partition of $\cup \{V(P^{ij}) \mid j \in I_i\}$.
Note that the resulting graph $G(\mathcal{I})$ is bipartite and has $\mathcal{O}(\text{poly}(n+m))$ vertices. Finally, set $k' = |R| + 4|I| + k$. We will show that $\mathcal{I} = (U, S, k)$ is a yes instance of the SET PACKING problem if and only if $\text{rk}(G(\mathcal{I})) \ge k'$.

Before going into the formal details, the intuition one may have, provided by the value of $k'$, is that a convexly independent set on at least $k'$ vertices, must necessarily be composed of all vertices of $R$, none of $U'$, union four or five vertices among $\{s'_i, s'_j\} \cup V(P^{ij}) \cup V(P^{ji})$, for every $\{i, j\} \in I$. The possible choice of such fifth vertex is what indicates the corresponding choice of a set $S_i$ to be part of a solution to the SET PACKING problem.

First, let $S' = \{S_{i_1}, \dots, S_{i_h}\}$ be pairwise non-intersecting sets of $S$. Let $I_S = \{i_1, \dots, i_h\}$ be the set of indices of such selected subsets. For every $j \in I_S'$, choose one arbitrary element of $A^j$ and name it $a_j$. Then, we claim that

$$X_0 = R \cup \left( \bigcup_{1 \le i \le m} (B^i \cup C^i) \right) \cup \{a_1, \dots, a_h\}$$

is a convexly independent set of cardinality $|X_0| = |R| + 4|I| + h$, and so if $(U, S, k)$ is a yes instance (so we may take $h \ge k$), then $\text{rk}(G(\mathcal{I})) \ge k'$.

Indeed<fnref n="1" />, note that $I(X_0) \setminus X_0 = \{s'_j | j \in I_S'\}$, as each such $s'_j$ lies in one (and only one) $C_4$ with $a_j$ and two other vertices, one of $B^j$ and the other of $C^j$, and they all belong to $X_0$. Then, observe that

$$I^2(X_0) \setminus I(X_0) = \left( \bigcup \{A^j | j \in I_S'\} \right) \setminus \{a_1, \dots, a_h\}$$

as the vertices $a^{jj'}$ lie in a $C_4$ with $s'_j, b^{jj'}$ and $c^{jj'}$, for every $j \in I_S'$ and every $j' \in I_j$. Note that $I^2(X_0)$ is then the convex hull of $X_0$ as no vertex in $V(G(\mathcal{I})) \setminus I^2(X_0)$ has two neighbors in one same connected component of $G(\mathcal{I})$[$I^2(X_0)$], since $S'$ is a solution to the SET PACKING problem. In particular, observe that the vertices in $U'$, in $\{s'_j | j \notin I_S'\}$ and in $\bigcup \{A^j | j \notin I_S'\}$ do not belong to $H(X_0)$.

Let $x \in X_0$. First of all, remind that $H(X_0 \setminus \{x\}) \subseteq H(X_0)$. Consequently, the vertices in $U'$, in $\{s'_j | j \notin I_S'\}$, and in $\bigcup \{A^j | j \notin I_S'\}$ do not belong to $H(X_0 \setminus \{x\})$. Thus, $x \notin H(X_0 \setminus \{x\})$, for any $x \in X_0$. Hence, $X_0$ is convexly independent.

Now, let $X$ be a convexly independent set of $G(\mathcal{I})$ such that

$$|X| \ge k' = |R| + 4|I| + k = 2|I| + n + m + 4|I| + k \ge 6|I| + n + m + 3,$$

as $k \ge 3$. W.l.o.g, assume that $X$ is maximal.

If $H(X) \cap U' \ne \emptyset$, since $n \ge 2$, then $|X \cap R| \le 2$ (see proof of Theorem 4). Thus

$$|X| \le 2 + |U'| + |S'| + 6|I| = 2 + 6|I| + n + m,$$

contradicting that $|X| \ge k'$. Hence, $H(X) \cap U' = \emptyset$ and so, since $X$ is maximal, we claim that $R \subseteq X$. Indeed, if $X$ is convexly independent, $H(X) \cap U' = \emptyset$ and $r \in R \setminus X$, then note that $X \cup \{r\}$ is convexly independent.

Therefore, from now on, assume that $H(X) \cap U' = \emptyset$ and $R \subseteq X$. Let us continue with the following remarks:

<footnote n="1">¹Recall that, for $S \subseteq V$, the interval $I(S)$ consists of $S$ and the set of vertices with at least two neighbours in a same component of $G[S]$.</footnote>
1. Note that, for every $1 \le i \le m$, if $s'_i \in X$, then for every $j \in I_i$, we have $|X \cap P^{ij}| \le 2$ since $s'_i \cup V(P^{ij})$ induces a cycle.

2. On the other hand, if $s'_i \notin X$, then $|X \cap (\bigcup_{j \in I_i} V(P^{ij}))| \le 2|I_i| + 1$. Indeed, otherwise, there exist $j, j'$ such that $P^{ij} \cup P^{j'i'} \subseteq X$, but since $s'_i \in H(V(P^{ij}))$, it follows easily that $X$ is not convexly independent as any vertex of $P^{ij'}$ belongs to such convex hull, a contradiction.

3. Then, let $\{i, j\} \in I$. Then, we claim that

$$|X \cap \left( \bigcup_{j' \in I_i} V(P^{ij'}) \cup \bigcup_{i' \in I_j} V(P^{j'i'}) \right)| \le 2(|I_i| + |I_j|) + 1.$$

Indeed, otherwise, by (2), there exists $i', j'$ such that $|X \cap P^{ij'}| = 3$ and $|X \cap P^{j'i'}| = 3$, in which case $X$ generates $s'_i$ and $s'_j$ which in turn generate a vertex of $U'$ corresponding to some element in $S_i \cap S_j$, contradicting that $H(X) \cap U' = \emptyset$.

4. If moreover, $s'_i \in X$, with similar arguments, we may deduce that

$$|X \cap \left( \bigcup_{j' \in I_i} V(P^{ij'}) \cup \bigcup_{i' \in I_j} V(P^{j'i'}) \right)| \le 2(|I_i| + |I_j|).$$

5. Now, let us assume that there exist $\{i, j\} \in I$ and $s'_i, s'_j \in X$. Let $u_r \in S_i \cap S_j$. In that case, we claim that $|X \cap V(P^{ij})| \le 1$ (and symmetrically $|X \cap V(P^{j'i})| \le 1$). Indeed, for purpose of contradiction, assume that $v, w \in X \cap V(P^{ij})$, then $V(P^{ij}) \subseteq H(\{s'_i, v, w\})$. Consequently, $u'_r \in H(\{s'_i, s'_j, a^{ij}\})$, contradicting that $H(X) \cap U' = \emptyset$.

Hence, if $X \cap S' = \emptyset$, by (2) and (3), $|X| \le |R| + 4|I| + k$.

Finally, let us assume that $Y = X \cap S' \ne \emptyset$. Let $Y_1 = \{s'_i \in Y \mid \forall s'_j \in Y \setminus \{s'_i\}, j \notin I_i\}$, let $Y_2 = Y \setminus Y_1$ (that is, $Y_1$ is the set of sets in $Y$ that are not intersecting with any of the sets in $Y$, while $Y_2$ is the set of sets in $Y$ that intersect at least one other set in $Y$), let $Y'_1 = \{s'_i \notin Y \mid \forall s'_j \in Y, j \notin I_i\}$ and $Y'_2 = S' \setminus (Y \cup Y'_1)$. Note that the elements in $Y_1 \cup Y'_1$ correspond to sets in $S$ that are pairwise disjoint and so $|Y_1 \cup Y'_1| \le k$.

By (1), for every $s'_i \in Y_1$, $|X \cap (\{s'_i\} \cup \bigcup_{j' \in I_i} P^{ij'})| \le 2|I_i| + 1$.

By (2), for every $s'_i \in Y'_1$, $|X \cap (\{s'_i\} \cup \bigcup_{j' \in I_i} P^{ij'})| \le 2|I_i| + 1$.

By (5), for every $s'_i \in Y_2$, $|X \cap (\{s'_i\} \cup \bigcup_{j' \in I_i} P^{ij'})| \le |I_i| + 1$.

By (4), for every $s'_i \in Y'_2$, $|X \cap (\{s'_i\} \cup \bigcup_{j' \in I_i} P^{ij'})| \le 2|I_i|$.

Overall, $|X| \le |R| + 4|I| - (\sum_{s'_i \in Y'_2} |I_i|) + |Y_1 \cup Y'_1| \le |R| + 4|I| + k = k'$. $\square$

### 3. Exact values and efficient algorithms for some graph classes

This section is devoted to proving that the rank can be computed in polynomial time in several graph classes such as Cartesian grids, chordal graphs, starlike graphs, and $(q, q-4)$-graphs.

#### 3.1. Cartesian grids

The cartesian product of $G$ and $H$, written $G \square H$ is the graph with vertex set $V(G) \times V(H)$ such that $(u, v)$ is adjacent to $(u', v')$ if and only if (1) $u = u'$ and $\{v, v'\} \in E(H)$, or (2) $v = v'$ and $\{u, u'\} \in E(G)$. The $n$-by-$m$ grid $G_{n \times m} = P_n \square P_m$ is defined as the Cartesian product of the
paths $P_n$ and $P_m$ on $n$ and $m$ vertices, respectively. Precisely, $G_{m \times n}$ is the grid with $m$ rows (with $n$ vertices) and $n$ columns (with $m$ vertices).

If $G$ is a grid, we use $L_i(G)$ (respectively, $C_i(G)$) to denote the set of vertices of row $i$ (respectively, column $i$). Moreover, we use $L_i^j(G)$ (respectively, $C_i^j(G)$) with $j \ge i$ to denote the set of vertices of $G$ from row $i$ to row $j$ (respectively, from column $i$ to column $j$). If $G$ is clear in the context, we may use directly $L_i, C_i, L_i^j, C_i^j$.

**Claim 3.** For any $n \in \mathbb{N}^*$, $rk(G_{1 \times n}) = n$. If $n \ge 2$, then $rk(G_{2 \times n}) = n + 1$.

*Proof.* The first statement is trivial. Let $n \ge 2$.

First, to prove that $rk(G_{2 \times n}) \ge n + 1$, observe that the set $S$ consisting of one row with $n$ vertices and one vertex in the other row is convexly independent.

The proof that $rk(G_{2 \times n}) \le n + 1$ is by induction on $n$. If $n = 2$, then the result holds since, clearly, $rk(G_{2 \times 2}) = 3$. Let $n > 2$ and assume by induction that the result holds for any grid $G_{2 \times n'}$ with $2 \le n' < n$. Let $S$ be convexly independent in $G_{2 \times n}$.

First, assume that there exists $1 \le i \le n$ such that no vertex of $S$ belongs to $C_i$. Let $G_L$ (resp., $G_R$) be the subgrid consisting of the $i-1$ first columns (resp, of the last $n-i$ columns). Possibly $G_L$ (if $i=1$) or $G_R$ (if $i=n$) may be empty. By Claim 1, $S_L = S \cap G_L$ and $S_R = S \cap G_R$ are convexly independent and so, by induction, $|S_L| \le i$ and $|S_R| \le n - i + 1$. Hence, $|S| = |S_L| + |S_R| \le n + 1$.

Second, assume that every column (with 2 vertices) intersects $S$. If $|S| \ge n+2$, then at least two columns are fully contained in $S$. Let $v$ be a vertex of a column fully included in $S$. Then, $S \setminus \{v\}$ contains at least one vertex per column, and at least one column has both its vertices in $S \setminus \{v\}$. Hence, observe that $H(S \setminus \{v\}) = V(G_{2 \times n})$ and so $v \in H(S \setminus \{v\})$, contradicting that $S$ is convexly independent. $\square$

The following observation is straightforward to check.

**Observation 9.** Let $G = G_{2 \times n}$ be a grid with $n \ge 2$ and let $S$ be a convexly independent set of $G$. If $|S| = n + 1$ and every column of $G$ contains a vertex of $S$, then $H(S) = V(G)$.

Let $G = G_{m \times n}$ be a grid with $n \ge m \ge 2$, and let $S$ be a convexly independent set of $G$. Define $X = \{i \mid C_i \cap S = \emptyset\}$ to be the set of column indices $i$ such that column $C_i$ contains no vertex from $S$. We say that $S$ is a *nice set* of $G$ if $X$ satisfies the following properties.

(i) $i \notin X$, for $i \in \{1, n\}$,

(ii) for every $2 \le i < n$, if $i \in X$ then $\{i-1, i+1\} \cap X = \emptyset$ (no two consecutive integers belong to $X$), and

(iii) $H(S) = V(G) \setminus (\bigcup_{i \in X} C_i)$.

Observe that (i) and (ii) imply that $|X| \le \lfloor \frac{n}{2} \rfloor - 1$; that is, there are at most $\lfloor \frac{n}{2} \rfloor - 1$ columns of $G$ containing no vertices of a nice set $S$.

Let $X = \{x_1, \dots, x_k\}$. We may assume without loss of generality that $x_1 < \dots < x_k$. Note that, for a nice set $S$, $H(S)$ induces $|X| + 1$ connected components, $G_1, \dots, G_{k+1}$, such that

$$V(G_1) = C_1^{x_1-1}, V(G_2) = C_{x_1+1}^{x_2-1}, \dots, V(G_{k+1}) = C_{x_k+1}^n.$$

We also say that $G_1, \dots, G_{k+1}$ are the $S$-components of $G$. Moreover, we define the *border columns* of an $S$-component $G_i$ as follows:
• if $1 < i < n$, then the border columns are $x_{i-1}$ and $x_i$;

• if $i = 1$, the border column is $x_1$;

• if $i = k + 1$, the border column is $x_k$.

See Fig. 2 for an example of a nice set.

<figure><img src="image_3.png" /><figcaption>Figure 2: Example of a nice set $S$ in the grid $G = G_{5,7}$. The vertices of $S$ are colored black. There are three $S$-components in $G$: $G_1 = G[C_1^2]$, $G_2 = G[C_4^5]$ and $G_3 = G[C_7]$.</figcaption></figure>

**Lemma 10.** Let $G = G_{2 \times n}$ be a grid with $n \ge 2$ and let $S$ be a convexly independent set of $G$. If $|S| = n + 1$, then $S$ is a nice set of $G$.

*Proof.* Let $X = \{x_1, \dots, x_k\}$ be the set of columns such that $C_{x_i} \cap S = \emptyset$ for every $1 \le i \le k$. We will show that $X$ is a set satisfying properties from (i) to (iii). Consequently, $S$ is a nice set.

We first prove that neither 1 nor $n$ belongs to $X$. Towards a contradiction, suppose that $1 \in X$ (the fact that $n \notin X$ is symmetric), that is, $S \cap C_1 = \emptyset$. Note that $G \setminus C_1$ induces a subgrid $G'$ of size $2 \times n-1$ and $|S| = |S \cap V(G')|$. By Claim 1 and Claim 3, it follows that $|S| \le n$, a contradiction.

Now we prove that there exists no $i$ such that $\{i, i+1\} \subseteq X$. Towards a contradiction, suppose that such an $i$ exists. Then, $G$ can be partitioned into two subgrids $G_1$ and $G_2$ of size $2 \times (i-1)$ and $2 \times (n-i-1)$, respectively. So $|S| = |S \cap V(G_1)| + |S \cap V(G_2)|$. By Claim 3, $|S \cap V(G_1)| \le i$ and $|S \cap V(G_2)| \le n-i$. So $|S| \le n$, a contradiction.

Thus, properties (i) and (ii) of a nice set are satisfied. Note that $G$ can be partitioned into $k+1$ subgrids $G_1, \dots, G_{k+1}$ of size $2 \times n_i$ where

• $n = k + \sum_{i=1}^{k+1} n_i$,

• $|S| = \sum_{i=1}^{k+1} |S \cap V(G_i)|$, and

• every column of $G_i$ has at least one vertex of $S$.

By Claim 3, it follows that $|S \cap V(G_i)| = n_i+1$; otherwise, $|S| \le \sum_{i=1}^{k+1} n_i + k = n$, a contradiction. Note that, by Observation 9, $|S \cap V(G_i)|$ is a hull set of $G_i$. Hence, property (iii) is satisfied. $\square$

**Observation 11.** Let $G = G_{m \times n}$ be a grid with $n \ge m \ge 2$. Let $S$ be a convexly independent set of $G$ and consider an integer $1 \le i \le n$. Suppose that $G'$ is a subgrid induced by $C_1^i$ and $S \cap V(G')$ is a hull set of $G'$. If there exists $i < j \le n$ such that $|C_j \cap S| \ge 2$, then there exists $i < \ell < j$ such that $|C_\ell \cap S| = 0$.
*Proof.* Indeed, let $i < \ell \le j$ be the smallest index such that $|C_\ell \cap S| \ne 1$. Since $S \cap C_1^i$ generates $G'$, then $H(S \cap C_1^{\ell-1}) = G[C_1^{\ell-1}]$. If $|S \cap C_\ell| > 1$, then consider a vertex $v \in S \cap C_\ell$, and it follows that $v \in H(S \cap C_1^\ell \setminus \{v\})$, since $S \cap C_1^\ell \setminus \{v\} \ne \emptyset$, contradicting that $S$ is convexly independent. Hence, if $|C_j \cap S| \ge 2$, then there must exist $|S \cap C_\ell| = 0$ with $i < \ell < j$. $\square$

The Observation 11 considers only columns of a grid, but one can easily check that the same argument is valid when applied to the rows.

**Lemma 12.** Let $G = G_{m \times n}$ be a grid with $n \ge m \ge 2$ and let $S$ be a convexly independent set of $G$. Let $G'$ be the subgrid induced by $L_1^{m-1}$. If $S' = S \cap V(G')$ is a nice set of $G'$, then there are no two distinct vertices of $S \cap L_m$, say $u$ and $v$, such that

(a) $u$ and $v$ are adjacent to the same $S'$-component of $G'$ or

(b) $u$ is adjacent to a $S'$-component $Y$ of $G'$ and $v$ belongs to a border column of $Y$.

In particular, $S \cap L_m$ is a stable set.

*Proof.* Let $G$ be a minimum counterexample to the statement. We may thus assume that there are only two $S'$-components $G'_1$ and $G'_2$ in $G'$ which implies, by the definition of a nice set, that there is exactly one column of $G'$ without vertices of $S$, say column $1 < \ell < n$. So $V(G'_1) = L_1^{m-1}(G') \cap C_1^{\ell-1}(G')$ and $V(G'_2) = L_1^{m-1}(G') \cap C_{\ell+1}^n(G')$.

Recall that, by the definition of a nice set, $S' \cap G_i$ is a hull set of $G'_i$ for $i \in \{1, 2\}$. Thus, by Observation 11 (applied to rows), it follows that $S \cap L_m$ has at most one vertex adjacent to each of $G'_1$ and $G'_2$, which proves property (a).

For purpose of contradiction, let us assume that there exist $v_\ell \in L_m \cap S \cap C_\ell$ and $v_i \in L_m \cap S \cap C_i$ with $i < \ell$ (the case $i > \ell$ is symmetric). Then, $S \cap C_1^\ell$ is a hull set of $G[C_1^\ell]$ and, because $S'$ is nice, $S' \cap V(G'_2)$ is a hull set of $V(G'_2)$. In particular, $|C_j \cap S| \ge 1$ for every $\ell < j \le n$. Indeed, since $m \ge 2$, there must exist $j \ge \ell + 1$ such that $v_{j1}, v_{j2} \in C_j(G) \cap S$. Hence, it is easy to check that $H(S \setminus \{v_{j1}\}) = V(G)$, in particular, it generates $v_{j1}$, contradicting that $S$ is convexly independent. Hence, (b) holds. $\square$

**Lemma 13.** Let $G_{m \times n}$ be a grid with $n \ge m \ge 3$. Let $S$ be a convexly independent set of $G$ such that $|S \cap (L_1 \cup L_2)| = n + 1$. Then either there is $3 \le k \le m$ such that $|L_k \cap S| < \lfloor \frac{n}{2} \rfloor$ or

(a) $|L_k \cap S| = \lfloor \frac{n}{2} \rfloor$ for every $3 \le k \le m$,

(b) $S$ is a nice set of $G$, and

(c) $G$ has exactly $\lfloor \frac{n}{2} \rfloor$ $S$-components.

*Proof.* Suppose that there is no $k$ with $3 \le k \le m$ such that $|L_k \cap S| < \lfloor \frac{n}{2} \rfloor$. We will prove properties (a), (b) and (c) by induction on $m$. Let $m \ge 3$, $S' = S \setminus L_m$ and $G' = G - L_m$. If $m = 3$, Lemma 10 ensures that $S'$ is a nice set of $G'$. If $m > 3$, by induction hypothesis, $S'$ is a nice set of $G'$ and $|L_k \cap S'| = |L_k \cap S| = \lfloor \frac{n}{2} \rfloor$ for every $3 \le k < m$. Hence, in both cases, Lemma 12 implies that $S \cap L_m$ is a stable set. Since $L_m$ induces a path with $n$ vertices and $|S \cap L_m| \ge \lfloor \frac{n}{2} \rfloor$, it follows that $|S \cap L_m| = \lfloor \frac{n}{2} \rfloor$, which proves property (a).

Let $X$ be the set of columns of $G'$ that do not contain a vertex of $S'$. Recall that by definition of a nice set, $X$ is exactly the set of columns that are border columns of some $S'$-component. Moreover, $|X| \le \lfloor \frac{n}{2} \rfloor - 1$ and the number of $S'$-components is $|X| + 1$. By Lemma 12 and the fact that $|S \cap L_m| = \lfloor \frac{n}{2} \rfloor$, $L_m \cap S$ must have exactly one vertex adjacent to each $S'$-component of $G'$. It is then easy to verify that this implies that $S$ is a nice set of $G$, which proves properties (b) and (c). $\square$
**Theorem 14.** Let $G_{m \times n}$ be a grid with $n \ge m \ge 2$. Then,

$$ \mathrm{rk}(G_{m \times n}) = f(n, m) = \begin{cases} \frac{mn}{2} + 1, & \text{for } m \text{ and } n \text{ both even,} \\ \frac{m(n+1)}{2}, & \text{for } m \text{ even, and } n \text{ odd} \\ \frac{(m+1)n}{2}, & \text{for } m \text{ odd.} \end{cases} $$

*Proof.* Let us first prove the lower bounds. If $n$ (number of columns) and $m$ (number of rows) are even, let $S = \{v\} \cup \bigcup_{1 \le i \le \frac{n}{2}} C_{2i-1}$ where $v$ is any vertex of $C_n$, then $S$ is convexly independent of size $\frac{nm}{2} + 1$. If $m$ is even and $n$ is odd, let $S = \bigcup_{1 \le i \le \frac{n+1}{2}} C_{2i-1}$, then $S$ is convexly independent of size $\frac{(n+1)m}{2}$. If $m$ is odd, let $S = \bigcup_{1 \le i \le \frac{m+1}{2}} L_{2i-1}$, then $S$ is convexly independent of size $\frac{(m+1)n}{2}$. See Fig. 3.

<figure><img src="image_4.png" /><figcaption>Figure 3: Grids $G_{4 \times 6}$, $G_{4 \times 7}$ and $G_{5 \times 7}$ and their respective convexly independent set colored black. On the left, with $m$ and $n$ even, $S = \{v\} \cup \bigcup_{1 \le i \le \frac{n}{2}} C_{2i-1}$. On center, for $m$ even and $n$ odd, $S = \bigcup_{1 \le i \le \frac{n+1}{2}} C_{2i-1}$. To the right, with $m$ odd, $S = \bigcup_{1 \le i \le \frac{m+1}{2}} L_{2i-1}$.</figcaption></figure>

Let us now prove the upper bounds.

We prove the result by induction on $m$. In $m = 2$, then the result follows by Claim 3. We may thus assume that $n \ge m \ge 3$. We shall analyze the following cases depending on the parity of $m$ and $n$.

**Case 1.** $m$ is even and $n$ is odd.

Note that $G$ can be partitioned into $k = \frac{m}{2}$ subgrids $G_1, \dots, G_k$ of size $2 \times n$. By induction hypothesis and Claim 1, $|S \cap G_i| \le n + 1$ for every $1 \le i \le k$. Therefore, $|S| \le \frac{m(n+1)}{2}$.

**Case 2.** $m$ and $n$ are both odd.

Suppose first that $|S \cap (L_1 \cup L_2)| \le n$. Let $G'$ be the subgrid induced by $L_3^m$. By the induction hypothesis, $|S \cap V(G')| \le \frac{(m-1)n}{2}$. Thus,

$$ |S| \le \frac{(m-1)n}{2} + n = \frac{(m+1)n}{2}. $$

Hence, we may assume that $|S \cap (L_1 \cup L_2)| = n + 1$. By Lemma 13 applied on the subgrid induced by $L_1^3$ and $S \cap L_1^3$, it follows that $|S \cap L_3| \le \lfloor \frac{n}{2} \rfloor$. So $G - L_3$ can be partitioned into $k = \frac{m-1}{2}$ subgrids $G_1, \dots, G_k$ of size $2 \times n$. By induction hypothesis and Claim 1, $|S \cap G_i| \le n + 1$ for every $1 \le i \le k$. Therefore,
$$
\begin{align*}
|S| &\le \frac{(m-1)(n+1)}{2} + |S \cap L_3| \\
&\le \frac{(m-1)(n+1)}{2} + \frac{n+1}{2} \\
&= \frac{m(n+1)}{2} \\
&\le \frac{(m+1)n}{2}, \quad \text{since } n \ge m.
\end{align*}
$$

**Case 3.** *m* and *n* are both even.

We first prove the following claim.

**Claim 4.** There exists an even $k$ with $2 \le k \le m$ such that $|S \cap L_1^k| \le \frac{kn}{2}$.

*Proof of Claim.* Towards a contradiction, suppose the opposite. This implies that $|S \cap (L_1 \cup L_2)| = n+1$ (because $|S \cap (L_1 \cup L_2)| > n$). By Claim 1 and Claim 3 and, by symmetry, $|S \cap (L_{m-1} \cup L_m)| = n+1$. Note that all arguments are symmetric by relabeling the rows of $G$.

Suppose first that there is even $k \in \{4, \dots, m-2\}$ such that $|S \cap (L_{k-1} \cup L_k)| \ne n$. Choose $k$ to be the smallest even integer satisfying such condition. If $|S \cap (L_{k-1} \cup L_k)| < n$, then

$$
|S \cap L_1^k| = |S \cap L_1^2| + |S \cap L_3^{k-2}| + |S \cap L_{k-1}^k| \le n+1 + \frac{(k-4)}{2}n + n-1 \le \frac{kn}{2},
$$

a contradiction to our assumption.

Otherwise, $|S \cap (L_{k-1} \cup L_k)| = n + 1$. In this case, let $G'$ be the subgrid induced by $L_1^k$. Note that

$$
|S \cap V(G')| = |S \cap L_1^2| + |S \cap L_3^{k-2}| + |L_{k-1}^k| = n + 1 + \frac{(k-4)n}{2} + n + 1 > \frac{kn}{2} + 1,
$$

a contradiction with our inductive hypothesis (since $k$ is even).

So we may assume that for every even $k \in \{4, \dots, m-2\}$, $|S \cap (L_{k-1} \cup L_k)| = n$. Now, we prove that there is no $i$ such that $|L_i \cap S| > \frac{n}{2}$ for $3 \le i \le m-2$. Towards a contradiction, suppose that such an $i$ exists. By symmetry of relabeling the rows of $G$, we may assume that $i$ is odd, and subject to that, $i$ is minimum. If $|S \cap L_j| = \frac{n}{2}$ for every $j < i$, then there is a contradiction to Lemma 13 (applied to $L_1^i$). Otherwise (because $i$ is minimum subject to being odd), there is even $4 \le j < i$ such that $|L_j \cap S| > \frac{n}{2}$. Let $\ell = i - j + 1$. Note that $\ell$ is even and $L_j^\ell$ induces a subgrid $H$ of size $\ell \times n$. Moreover, $|H \cap S| > 2(\frac{n}{2} + 1) + \frac{(\ell-2)n}{2} > \frac{\ell n}{2} + 1$, a contradiction with the induction hypothesis.

Hence, we may assume that $|S \cap L_i| = \frac{n}{2}$ for every $3 \le i \le m-2$. By Lemma 13 applied to $G[L_1^{m-2}]$, $G$ has exactly $\frac{n}{2}$ $S$-components. Since $|S \cap (L_1 \cup L_2)| = n+1$ and $|S \cap (L_{m-1} \cup L_m)| = n+1$, it follows that either (a) $|L_{m-1} \cap S| \ge \frac{n}{2} + 1$ or (b) $|L_{m-1} \cap S| = \frac{n}{2}$ and $|L_m \cap S| = \frac{n}{2} + 1$. If (a), then $S \cap L_1^{m-1}$ is a nice set of the subgrid induced by $L_1^{m-1}$ which gives us a contradiction to Lemma 13. If (b), then $G$ and $S$ give a contradiction to Lemma 13. $\diamond$

By the previous claim, we may assume that there is even $k$ such that $|S \cap L_1^k| \le \frac{kn}{2}$. Let $G'$ be the subgrid induced by $L_{k+1}^m$. By induction hypothesis, $|S \cap V(G')| \le \frac{(m-k)n}{2} + 1$. Hence,
$$|S| \le \frac{(m-k)n}{2} + 1 + \frac{kn}{2} \le \frac{mn}{2} + 1.$$

This completes the proof of the theorem. □

### 3.2. Chordal graphs

In this section, we show that the rank of chordal graphs can be computed in polynomial time. Note that, by Observation 2, the cycle convexity coincides with $\Delta$-convexity in chordal graphs (in the $\Delta$-convexity, the interval of a set $S \subseteq V$ consists of the union of $S$ with every vertex that is adjacent to two adjacent vertices in $S$ [35]). The rank of $\Delta$-convexity has been shown to be polynomial solvable in 2-connected chordal graphs and block graphs (where each 2-connected component induces a clique) in [31]. Here, we solve the problem in any chordal graph.

For completeness, and because it is important in the remaining of this section, we start with the easy case of 2-connected chordal graphs. The more general case of connected chordal graphs relies on a non-trivial dynamic programming algorithm over its block (2-connected component) decomposition.

Recall that a set $S \subseteq V$ generates $v \in V$ (resp., $Y \subseteq V$) if $v \in H(S)$ (resp. if $Y \subseteq H(S)$). Recall also that, in chordal graphs, the maximum (weighted) independent set problem can be solved in polynomial time [36].

**Lemma 15.** [31] Let $G$ be a 2-connected chordal graph. Then,

$$\mathrm{rk}(G) = \max\{2, \alpha(G)\}.$$

*Proof.* It is clear that $\mathrm{rk}(G) \ge \max\{2, \alpha(G)\}$ and $\mathrm{rk}(G) = 2$ if $G$ is a complete graph. Let us assume that $G$ is not a complete graph. Note that, for every $u, v \in E(G)$, it holds that $H(\{u, v\}) = V(G)$. Indeed, this comes easily by induction, by considering $G-w$ where $w$ is any simplicial vertex distinct from $u$ and $v$. Hence, every convexly independent set with at least three vertices must be a stable set, which concludes the proof. □

The key point that will be widely used below is that, for any convexly independent set $S$ of a 2-connected chordal graph, the following holds:

**Observation 16.** - $H(S) = V(G)$ if and only if $S$ induces a $K_2$, and

- $H(S) \neq V(G)$ if and only if $S$ is a stable set. In particular, in this case, $H(S) = S$.

Let $G$ be any connected chordal graph and let $B$ be any block of it. Let $v_1, \dots, v_d$ be the cut-vertices of $G$ that belong to $B$. For every $1 \le i \le d$, let $C'_i$ be the union of the vertex sets of the connected components of $G-v_i$ that do not intersect $B$ and let $G_i$ be the subgraph of $G$ induced by $C'_i \cup \{v_i\}$. With a slight abuse of notation, in the sequel sometimes we use only $G_i$ to actually refer to $V(G_i)$. Let $Q$ be any convexly independent set of $G$. For every $1 \le i \le d$, let $Q_i = Q \cap V(G_i)$ and let $Q_B = Q \cap (B \setminus \{v_1, \dots, v_d\})$. Note that $\{Q_i \mid 1 \le i \le d\} \cup \{Q_B\}$ is a partition of $Q$. To give some intuition on the forthcoming algorithm, let us list the possibly different cases for $Q_B$, ensuring that $Q$ is convexly independent.

1. Either there exist $1 \le i < j \le d$, $v_i, v_j \in E(G)$ and $v_i \in H_{G_i}(Q_i)$ (where $H_{G_i}(Q_i)$ denote the convex hull of $Q_i$ in $G_i$) and $v_j \in H_{G_j}(Q_j)$, then $Q \cap (B \setminus \{v_i, v_j\}) = \emptyset$. Moreover, for every $h \in \{1, \dots, d\} \setminus \{i, j\}$ and for every $w \in Q_h \setminus \{v_h\}$, we have $w \notin H_{G_h}(Q_h \cup \{v_h\} \setminus \{w\})$, or
2. there exists $1 \le i \le d$, such that $v_i \in H_{G_i}(Q_i)$ and $v_i$ is adjacent to some vertex of $Q_B$. In this case, $|Q \cap B \setminus \{v_i\}| = 1$. Moreover, for every $h \in \{1, \dots, d\} \setminus \{i\}$ and for every $w \in Q_h \setminus \{v_h\}$, we have $w \notin H_{G_h}(Q_h \cup \{v_h\} \setminus \{w\})$, or

3. there exist $u, v \in Q_B$ with $u, v \in E(G)$; in this case, $Q_B = \{u, v\}$ and, for every $h \in \{1, \dots, d\}$ and for every $w \in Q_h \setminus \{v_h\}$, we have $w \notin H_{G_h}(Q_h \cup \{v_h\} \setminus \{w\})$, or

4. let $I \subseteq \{1, \dots, d\}$ such that $i \in I$ if and only if $v_i \in H_{G_i}(Q_i)$, then $Q_B \cup \{v_i | i \in I\}$ is a stable set of $B$.

Note that the first three cases correspond to the cases when $B \subseteq H(Q)$ (by Observation 16). In the discussion above, it naturally appears a notion that we formalize here. Given a graph $G = (V, E)$, a set $Q \subset V$ and a vertex $v \notin Q$, we say that $Q$ is *v-protected* if $Q$ is convexly independent and, for every $w \in Q$, it holds that $w \notin H(Q \cup \{v\} \setminus \{w\})$.

To compute the rank of chordal graphs, we present a dynamic programming algorithm that will need to compute more information at every step. For this, we introduce the following notation that is guided by the above cases. For every graph $G$ and $v \in V(G)$,

* let $r_v(G, v)$ be the maximum size of a convexly independent set $Q$ of $G$ among those which contain $v$ (i.e., $v \in Q$);

* let $r_{\bar{v}h}(G, v)$ be the maximum size of a convexly independent set $Q$ of $G$ among those which do not contain $v$ but generate $v$ (i.e., $v \notin Q$ and $v \in H(Q)$);

* let $r_{\bar{v}\bar{h}}(G, v)$ be the maximum size of a convexly independent set $Q$ of $G$ among those which do not contain $v$ and do not generate $v$ (i.e., $v \notin Q$ and $v \notin H(Q)$);

* let $r_{\bar{v}\bar{h}p}(G, v)$ be the maximum size of a convexly independent set $Q$ such that, $v \notin Q$ and $v$ is not generated by $Q$ ($v \notin H(Q)$) and $Q$ is *v-protected*, and

* let $r_{\bar{v}hp}(G, v)$ be the maximum size of a convexly independent set $Q$ such that, $v \notin Q$ and $v$ is generated by $Q$ ($v \in H(Q)$) and $Q$ is *v-protected*.

The indices $v, h, p$ denote respectively whether $v$ belongs to $Q$, to the convex hull of $Q$ and $Q$ is *v-protected*, or not, if there is a “bar” above the letter. Note that, by definition,

$$ \mathrm{rk}(G) = \max\{r_v(G, v), r_{\bar{v}h}(G, v), r_{\bar{v}\bar{h}}(G, v)\}. $$

The following claim is straightforward.

**Claim 5.** Let $G$ be any graph with a bridge $e = \{u, v\} \in E(G)$ and let $G_1, G_2$ be the two components of $G - e$, then $\mathrm{rk}(G) = \mathrm{rk}(G_1) + \mathrm{rk}(G_2)$.

**Theorem 17.** The rank can be computed in polynomial time in the class of chordal graphs.

*Proof.* By Claim 5 and Lemma 5, we may only consider connected bridgeless chordal graphs.

We design a dynamic programming algorithm that, given a bridgeless chordal graph $G$ and a vertex $v \in V(G)$, computes in polynomial time each of the parameters $r_v(G, v)$, $r_{\bar{v}h}(G, v)$, $r_{\bar{v}\bar{h}}(G, v)$, $r_{\bar{v}\bar{h}p}(G, v)$ and $r_{\bar{v}hp}(G, v)$, and corresponding convexly independent sets. In other words, for every $\beta \in \{r_v(G, v), r_{\bar{v}h}(G, v), r_{\bar{v}\bar{h}}(G, v), r_{\bar{v}\bar{h}p}(G, v), r_{\bar{v}hp}(G, v)\}$, our algorithm keeps a convexly independent set, satisfying the corresponding constraints, of size $\beta$.
This algorithm relies on the block decomposition of $G$, which can be computed in polynomial time. Furthermore, recall that a maximum weighted stable set (so, in particular, $\alpha(G)$) can be computed in polynomial time if $G$ is chordal [36].

We proceed by induction on the number $b \ge 1$ of blocks.

**Base case:** $G$ is 2-connected, i.e., $b = 1$. By Lemma 15, $rk(G) = \max\{2, \alpha(G)\}$. Using similar arguments, it can be shown that $r_v(G, v) = \max\{2, 1+\alpha(G-N[v])\}$ (where $N[v] = N(v) \cup \{v\}$ is the closed neighbourhood of $v$) as a maximum convexly independent set containing $v$ is either any edge containing $v$ or any maximum stable set among those that contain $v$. Because of Observation 16, $r_{\bar{v}h}(G, v) = 2$ and such a convexly independent set is any edge not containing $v$. Also, one can observe that, $r_{\bar{v}h}(G, v) = \alpha(G-v)$, i.e., any maximum stable set among those that do not contain $v$ is a maximum convexly independent set that does not generate $v$. Then, $r_{\bar{v}hp}(G, v) = \alpha(G-N[v])$ if $G-N[v]$ contains a stable set of size at least 2, otherwise $r_{\bar{v}hp}(G, v) = 1$ (any vertex of $G-v$ being such a set). Finally, if there exists an edge with no endpoint in $N[v]$ $r_{\bar{v}hp}(G, v) = 2$ and $r_{\bar{v}hp}(G, v) = 0$ otherwise.

Now, let $b > 1$ be the number of blocks of $G$. By induction on $b$, let us assume that for every bridgeless chordal graph $G'$ with at most $b-1 \ge 1$ blocks and for every and $v' \in V(G')$, $r_v(G', v')$, $r_{\bar{v}h}(G', v')$, $r_{\bar{v}h}(G', v')$, $r_{\bar{v}hp}(G', v')$ and $r_{\bar{v}hp}(G', v')$ can be computed in polynomial time in the size of $G'$.

Now, provided an arbitrary vertex $v \in V(G)$, let us compute the same parameters with respect to $(G, v)$. There are two cases to be considered.

**Case 1) First, consider the case in which $v$ is a cut-vertex.** Let us assume that $v$ is a cut-vertex, that $C'_1, \dots, C'_l$ are the connected components of $G-v$ and, that $G_i = G[C'_i \cup \{v\}]$, for every $1 \le i \le l$. Then, for every $1 \le i \le l$, let us assume that $r_v(G_i, v)$, $r_{\bar{v}h}(G_i, v)$, $r_{\bar{v}h}(G_i, v)$, $r_{\bar{v}hp}(G_i, v)$ and $r_{\bar{v}hp}(G_i, v)$ and a corresponding set for each parameter have been computed recursively. Then,

1. $r_v(G, v) = (\sum_{1 \le i \le l} r_v(G_i, v)) - l + 1$, and the corresponding set being the union of the corresponding sets, each of them containing $v$, in the $G_i$'s.

2. Similarly, $r_{\bar{v}h}(G, v) = \sum_{1 \le i \le l} r_{\bar{v}h}(G_i, v)$, the corresponding set being the union of the corresponding sets, each of them not containing nor generating $v$, in the $G_i$'s.

3. Similarly, $r_{\bar{v}hp}(G, v) = \sum_{1 \le i \le l} r_{\bar{v}hp}(G_i, v)$.

4. $r_{\bar{v}hp}(G, v) = \max_{1 \le i \le l}\{r_{\bar{v}hp}(G_i, v) + \sum_{j \ne i} \max\{r_{\bar{v}hp}(G_j, v), r_{\bar{v}hp}(G_j, v)\}\}$.

Indeed, any set of $G$ not containing $v$, generating $v$ in $G$ and $v$-protected must consist of a subset not containing but generating $v$ and $v$-protected in $G_i$ for some $1 \le i \le l$ and of subsets not containing $v$ that are $v$-protected in each of the $G_j$'s, for $j \ne i$, $1 \le j \le l$.

5. Finally,

$$r_{\bar{v}h}(G, v) = \max\{r_{\bar{v}hp}(G, v), \max_{1 \le i \le l}\{r_{\bar{v}h}(G_i, v) + \sum_{j \ne i} r_{\bar{v}hp}(G_j, v)\}\}.$$

Note that any set of $G$ not containing $v$ and generating $v$ in $G$ is either $v$-protected (case above) or must consist of exactly one subset, contained in some component $C_i$, not containing but generating $v$ and not $v$-protected in $G_i$ for some $1 \le i \le l$ and of subsets, not containing nor generating $v$, that are $v$-protected in each of the $G_j$'s, for $j \ne i$. In other words, given a convexly independent set $Q$ not containing $v$ but generating it and not $v$-protected, there must be at most one restriction $Q_i = Q \cap G_i$ of $Q$ to $G_i$ that can be not $v$-protected in $G_i$; otherwise $Q$ would not be convexly independent.
**Case 2) Second, $v$ is not a cut-vertex of $G$.** Let $B$ be the block containing $v$. As above, let $v_1, \dots, v_\ell$ be the cut-vertices of $G$ that belong to $B$. For every $1 \le i \le \ell$, let $C'_i$ be the union of the connected components of $G - v_i$ that do not intersect $B$ and let $G_i$ be the subgraph of $G$ induced by $V(C'_i) \cup \{v_i\}$. Then, for every $1 \le i \le \ell$, let us assume that $r_v(G_i, v_i)$, $r_{\bar{v}h}(G_i, v_i)$, $r_{\bar{v}\bar{h}}(G_i, v_i)$, $r_{\bar{v}\bar{h}p}(G_i, v_i)$, and $r_{\bar{v}hp}(G_i, v_i)$ and one corresponding set for each parameter have been computed recursively.

Let us describe how to extend these results to compute the different desired sets for $(G, v)$. Our algorithm will compute such parameters and corresponding sets by a case analysis: first it verifies possible maximum convexly independent sets $Q$ such that $B \subseteq H(Q)$, in which case $|Q \cap B| \le 2$, and thus it proceeds by brute-force; then it looks for maximum convexly independent sets $Q$ such that $B \not\subseteq H(Q)$, in which case $|Q \cap B|$ is a stable set, by Observation 16.

**Convexly independent sets of $G$ not intersecting $B \setminus \{v_1, \dots, v_\ell\}$ and generating $B$.** For such sets $Q$, by Observation 16, there must be $1 \le i < j \le \ell$, such that $\{v_i, v_j\} \in E(G)$ and $v_i$ (resp., $v_j$) contained in $Q$ or generated by $Q_i = Q \cap G_i$ (resp., by $Q_j = Q \cap G_j$).

Here, we show that computing such a maximum set $Q$ can be done in polynomial time.

* We first explain how to compute several sets that will be useful in the computation of $r_{\bar{v}h}(G, v)$. There are several cases to be considered.

More in details, in what follows, we will first compute (Subcase 1 below), for every two adjacent cut-vertices $v_i$ and $v_j$, a maximum convexly independent set $Q_{i,j}$ of $G$ among those that contains $v_i$ and $v_j$. Note that since $v_i$ and $v_j$ are adjacent, they will generate $B$, so we need to ensure that all cut-vertices $v_t$ ($t \notin \{i, j\}$) are protected in $G_t$ for $Q_{i,j}$ to be convexly independent. We also need that no two generated cut-vertices, and no generated cut-vertex and $v_j$ (resp. $v_i$) are adjacent since otherwise they would generate $v_i$ (resp., $v_j$). Hence, all cut-vertices that are generated by their own component (by $G_t \cap Q_{i,j}$) must be a stable set of $B$ and must be non-adjacent to $v_i$ and $v_j$. Finally, for $Q_{i,j}$ to be maximum, this stable set must be maximum (under some criteria defined below) and $Q_{i,j} \cap G_t$ must be a maximum convexly independent set of $G_t$ generating or containing or not generating $v_t$, depending on whether $t \in \{i, j\}$ and on whether we aim $v_t$ to be generated.

Then (Subcase 2 below), we compute, for every two adjacent cut-vertices $v_i$ and $v_j$, a maximum convexly independent set $Q_{i,j}$ of $G$ among those that contain $v_i$ and not contain $v_j$, but such that $v_j$ is generated by $Q_{i,j} \cap G_j$. The constraints are the same as in previous subcase: the other generated cut-vertices must induce a stable set, but this time, they might be adjacent to $v_i$ since their is no risk in generating $v_j$.

Subcases 3 to 5 proceed similarly by considering other kinds of maximum convexly independent set not intersecting $B \setminus \{v_1, \dots, v_\ell\}$ and generating $B$.

The key is that a maximum convexly independent set not intersecting $B \setminus \{v_1, \dots, v_\ell\}$ and generating $B$ will be a largest set among the ones computed, which will give us the value of $r_{\bar{v}h}(G, v)$. The other parameters are computed similarly later on. Note that there are a polynomial number of sets we aim at computing and, as shown below, each of them can be computed in polynomial time. Hence, the time-complexity of the algorithm is polynomial.

1. Let us first consider such convexly independent set $Q_{i,j}$ of $G$ such that $|Q_{i,j} \cap B| = 2$. Let $\{v_i, v_j\} \in E(G)$ such that $v_i$ and $v_j$ belong to $Q_{i,j}$ (there are at most $O(\ell^2)$ such
possibilities). So, for each such pair {$i, j$}, we do the following (and keep a largest set among the ones we obtain).

Note that $Q_{i,j} \cap G_t$, for each $t \in \{i, j\}$, must be a convexly independent set of $G_t$ of size $r_v(G_t, v_t)$, and such sets have been computed recursively.

Moreover, for every $t \in \{1, \dots, \ell\} \setminus \{i, j\}$ such that $Q_{i,j} \cap G_t$ generates $v_t$, we have to ensure that no generated $v_t$ will, in turn, generate $v_i$ or $v_j$ (for the set $Q_{i,j}$ to be convexly independent). For that, we need that all such generated $v_t$ are pairwise non adjacent and non adjacent to both $v_i$ and $v_j$. Note also that, for all $t \in \{1, \dots, \ell\} \setminus \{i, j\}$, $Q_{i,j} \cap G_t$ must be $v_t$-protected since $v_t$ will be generated by $\{v_i, v_j\}$ and so, $Q_{i,j} \cap G_t$ must be a set of size $r_{\bar{v}hp}(G_t, v_t)$ (if it does not generate $v_t$) or $r_{\bar{v}hp}(G_t, v_t)$ (if it generates $v_t$).

Note that combining solutions $Q_{i,j} \cap G_t$ not generating $v_t$ and of size $r_{\bar{v}hp}(G_t, v_t)$, for all $t \in \{1, \dots, \ell\} \setminus \{i, j\}$, would produce a feasible convexly independent set. Intuitively, to improve on that, we need to consider the gain of taking a set $Q_{i,j} \cap G_t$ generating $v_t$ of size $r_{\bar{v}hp}(G_t, v_t)$ for those $t \in \{1, \dots, \ell\} \setminus \{i, j\}$ with $r_{\bar{v}hp}(G_t, v_t) - r_{\bar{v}hp}(G_t, v_t) > 0$. More precisely, to compute such a set $Q_{i,j}$ with maximum size, we continue as follows.

Let $T^* \subseteq \{1, \dots, \ell\} \setminus \{i, j\}$ be such that $t \in T^*$ if and only if $r_{\bar{v}hp}(G_t, v_t) > r_{\bar{v}hp}(G_t, v_t)$.

We must find a subset of $\{v_t \mid t \in T^*\} \setminus (N[v_i] \cup N[v_j])$ that is a stable set in $B \setminus (N[v_i] \cup N[v_j])$; note that this must be a stable set to ensure the convex independence.

To compute such a set, compute a maximum weighted stable set $S'$ in the chordal graph induced by $\{v_t \mid t \in T^*\} \setminus (N[v_i] \cup N[v_j])$ where each vertex $v_t$ has weight $r_{\bar{v}hp}(G_t, v_t) - r_{\bar{v}hp}(G_t, v_t) > 0$. Let $S \subseteq T^*$ be the set of indices of the vertices in $S'$. Then, for every vertex $v_t$, with $t \in S$, $Q_{i,j} \cap G_t$ must be a set of size $r_{\bar{v}hp}(G_t, v_t)$ (in $G_t$), and for every $t \in \{1, \dots, \ell\} \setminus (\{i, j\} \cup S)$, the set $Q_{i,j} \cap G_t$ must have size $r_{\bar{v}hp}(G_t, v_t)$.

2. Second, let us consider such convexly independent set $Q_{i,j}$ of $G$ such that $|Q_{i,j} \cap B| = 1$. For every $\{v_i, v_j\} \in E(G)$ (there are at most $O(\ell^2)$ such possibilities), let us consider a set $Q_{i,j}$ such that $v_i \in Q_{i,j}$ and $v_j$ is generated by $Q_{i,j} \cap G_j$ but not necessarily protected. So, for each such pair {$i, j$}, we do the following while keeping a largest set among the ones we obtain.

In that subcase 2, a desired set $Q_{i,j}$ must be such that $|Q_{i,j} \cap G_i| = r_v(G_i, v_i)$ and $|Q_{i,j} \cap G_j| = r_{\bar{v}h}(G_j, v_j)$.

Moreover, for every $t \in \{1, \dots, \ell\} \setminus \{i, j\}$ such that $Q_{i,j} \cap G_t$ generates $v_t$, we have to ensure that no generated $v_t$ will, in turn, generate $v_i$ (for the set $Q_{i,j}$ to be convexly independent). For that, we need that all such generated $v_t$, including $v_j$, are pairwise non adjacent. Note also that, for all $t \in \{1, \dots, \ell\} \setminus \{i, j\}$, $Q_{i,j} \cap G_t$ must be a set of size $r_{\bar{v}hp}(G_t, v_t)$ (if it does not generate $v_t$) or $r_{\bar{v}hp}(G_t, v_t)$ (if it generates $v_t$) and $Q_{i,j} \cap G_t$ must be $v_t$-protected since $v_t$ will be generated by $\{v_i, v_j\}$. To compute such a set $Q_{i,j}$ with maximum size, we continue as follows.

Let $T^* \subseteq \{1, \dots, \ell\} \setminus \{i, j\}$ be such that $t \in T^*$ if and only if $r_{\bar{v}hp}(G_t, v_t) > r_{\bar{v}hp}(G_t, v_t)$.

We must find a subset of $\{v_t \mid t \in T^*\} \setminus (\{v_i\} \cup N[v_j])$ that is a stable set in $B \setminus (\{v_i\} \cup N[v_j])$. Note that this must be a stable set to ensure the convex independence and in particular, in this case, this stable set may contain vertices in the neighbourhood of $v_i$.

To compute such a set, compute a maximum weighted stable set $S'$ in the chordal graph induced by $\{v_t \mid t \in T^*\} \setminus (\{v_i\} \cup N[v_j])$ where each vertex $v_t$ has weight $r_{\bar{v}hp}(G_t, v_t) - r_{\bar{v}hp}(G_t, v_t)$. Let $S \subseteq T^*$ be the set of indices of the vertices in $S'$. Then, for every vertex $v_t$, with $t \in S$, $Q_{i,j} \cap G_t$ must be a set of size $r_{\bar{v}hp}(G_t, v_t)$ in $G_t$, and for every $t \in \{1, \dots, \ell\} \setminus (\{i, j\} \cup S)$, the set $Q_{i,j} \cap G_t$ must have size $r_{\bar{v}hp}(G_t, v_t)$.
3. The next three subcases (3 to 5) consider such convexly independent set $Q_{i,j}$ of $G$ such that $Q_{i,j} \cap B = \emptyset$.

This subcase 3 considers such convexly independent set $Q_{i,j}$ of $G$ such that there is a pair $\{i,j\}$ (there are at most $O(\ell^2)$ such possibilities) such that $\{v_i, v_j\} \in E(G)$, neither $v_i$ nor $v_j$ are contained in $Q_{i,j}$, both are generated by $Q_{i,j}$, and $Q_{i,j} \cap G_i$ is not necessarily $v_i$-protected in $G_i$ and $Q_{i,j} \cap G_j$ is not necessarily $v_j$-protected in $G_j$.

In that case, a desired set $Q_{i,j}$ must be such that $|Q_{i,j} \cap G_i| = r_{\bar{v}h}(G_i, v_i)$ and $|Q_{i,j} \cap G_j| = r_{\bar{v}h}(G_j, v_j)$.

Moreover, for every $t \in \{1, \dots, \ell\} \setminus \{i, j\}$, $Q_{i,j} \cap G_t$ must be a set of size $r_{\bar{v}\bar{h}p}(G_t, v_t)$ (if it does not generate $v_t$) or $r_{\bar{v}hp}(G_t, v_t)$ (if it generates $v_t$). Note that, for all $t \in \{1, \dots, \ell\} \setminus \{i, j\}$, $Q_{i,j} \cap G_t$ must be $v_t$-protected in $G_t$ since $v_t$ will be generated by $\{v_i, v_j\}$. Moreover, we have to ensure that those generated $v_t$ will not, in turn, generate $v_i$ nor $v_j$ (since $Q_{i,j} \cap G_i$ is not necessarily $v_i$-protected and similarly $Q_{i,j} \cap G_j$ is not necessarily $v_j$-protected).

Let $T^* \subseteq \{1, \dots, \ell\} \setminus \{i, j\}$ be such that $t \in T^*$ if and only if $r_{\bar{v}hp}(G_t, v_t) > r_{\bar{v}\bar{h}p}(G_t, v_t)$. We must find a subset of $\{v_t \mid t \in T^*\} \setminus (N[v_i] \cup N[v_j])$ that is a stable set in $B \setminus (N[v_i] \cup N[v_j])$, note that this must be a stable set to ensure the convex independence. To compute such a set, compute a maximum weighted stable set $S'$ in the chordal graph induced by $\{v_t \mid t \in T^*\} \setminus (N[v_i] \cup N[v_j])$ where each vertex $v_t$ has weight $r_{\bar{v}hp}(G_t, v_t) - r_{\bar{v}\bar{h}p}(G_t, v_t)$. Let $S \subseteq T^*$ be the set of indices of the vertices in $S'$. Then, for every vertex $v_t$, with $t \in S$, $Q_{i,j} \cap G_t$ must be a set of size $r_{\bar{v}hp}(G_t, v_t)$ (in $G_t$), and for every $t \in \{1, \dots, \ell\} \setminus (\{i, j\} \cup S)$, the set $Q_{i,j} \cap G_t$ must have size $r_{\bar{v}\bar{h}p}(G_t, v_t)$.

4. Then, this subcase considers such convexly independent set $Q_{i,j}$ of $G$ such that there is a pair $\{i,j\}$ (there are at most $O(\ell^2)$ such possibilities) such that $\{v_i, v_j\} \in E(G)$, neither $v_i$ nor $v_j$ are contained in $Q_{i,j}$, both are generated by $Q_{i,j}$, but $Q_{i,j} \cap G_i$ is not necessarily $v_i$-protected while $Q_{i,j} \cap G_j$ is $v_j$-protected.

In that case, a desired set $Q_{i,j}$ must be such that $|Q_{i,j} \cap G_i| = r_{\bar{v}h}(G_i, v_i)$ and $|Q_{i,j} \cap G_j| = r_{\bar{v}hp}(G_j, v_j)$.

Moreover, for every $t \in \{1, \dots, \ell\} \setminus \{i, j\}$, $Q_{i,j} \cap G_t$ must be a set of size $r_{\bar{v}\bar{h}p}(G_t, v_t)$ (if it does not generate $v_t$) or $r_{\bar{v}hp}(G_t, v_t)$ (if it generates $v_t$). Note that, for all $t \in \{1, \dots, \ell\} \setminus \{i, j\}$, $Q_{i,j} \cap G_t$ must be $v_t$-protected since $v_t$ will be generated by $\{v_i, v_j\}$. Moreover, we have to ensure that those generated $v_t$ will not, in turn, generate $v_i$, since $Q_{i,j} \cap G_i$ is not necessarily $v_i$-protected.

Let $T^* \subseteq \{1, \dots, \ell\} \setminus \{i, j\}$ be such that $t \in T^*$ if and only if $r_{\bar{v}hp}(G_t, v_t) > r_{\bar{v}\bar{h}p}(G_t, v_t)$. We must find a subset of $\{v_t \mid t \in T^*\} \setminus (\{v_i\} \cup N[v_j])$ that is a stable set in $B \setminus (\{v_i\} \cup N[v_j])$, note that this must be a stable set to ensure the convex independence. To compute such a set, compute a maximum weighted stable set $S'$ in the chordal graph induced by $\{v_t \mid t \in T^*\} \setminus (\{v_i\} \cup N[v_j])$ where each vertex $v_t$ has weight $r_{\bar{v}hp}(G_t, v_t) - r_{\bar{v}\bar{h}p}(G_t, v_t)$. Let $S \subseteq T^*$ be the set of indices of the vertices in $S'$. Then, for every vertex $v_t$, with $t \in S$, $Q_{i,j} \cap G_t$ must be a set of size $r_{\bar{v}hp}(G_t, v_t)$ (in $G_t$), and for every $t \in \{1, \dots, \ell\} \setminus (\{i, j\} \cup S)$, the set $Q_{i,j} \cap G_t$ must have size $r_{\bar{v}\bar{h}p}(G_t, v_t)$.

5. In this last subcase, we consider such convexly independent set $Q_{i,j}$ of $G$ such that there is a pair $\{i,j\}$ (there are at most $O(\ell^2)$ such possibilities) such that $\{v_i, v_j\} \in E(G)$, neither $v_i$ nor $v_j$ are contained in $Q_{i,j}$, both are generated by $Q_{i,j}$ and $Q_{i,j} \cap G_i$ is $v_i$-protected and $Q_{i,j} \cap G_j$ is $v_j$-protected.
In that case, a desired set $Q_{i,j}$ must be such that $|Q_{i,j} \cap G_i| = r_{\bar{v}hp}(G_i, v_i)$ and $|Q_{i,j} \cap G_j| = r_{\bar{v}hp}(G_j, v_j)$. Moreover, we add to it the union of the convexly independent sets $Q_t$ of $G_t$ of size $\max\{r_{\bar{v}hp}(G_t, v_t), r_{\bar{v}hp}(G_t, v_t)\}$ (with $Q_t$ satisfying the corresponding constraints) for every $t \in \{1, \dots, \ell\} \setminus \{i, j\}$.

Hence, a largest set among the ones computed in the five items above will be a largest convexly independent set not intersecting $B \setminus \{v_1, \dots, v_\ell\}$ and generating $B$.

* The sets computed in the previous item will be considered in the computation of $r_{\bar{v}h}(G, v)$. To compute $r_{\bar{v}hp}(G, v)$, we will also need information about the sets not containing $v$, generating $v$ and $v$-protected. Such sets are similar to those described in the previous item, with the extra constraint that, no vertex $u \in Q_{i,j}$ is generated by $Q_{i,j} \cup \{v\} \setminus \{u\}$. More precisely, the differences with above are as follows.

- In subcase 1 above, when $v_i, v_j \in Q_{i,j}$, we must only consider the cases when $v_i \notin N(v)$ and $v_j \notin N(v)$ and, for every $t \in \{1, \dots, \ell\} \setminus \{i, j\}$ with $v_t \in N(v)$, $Q_{i,j} \cap G_t$ must not generate $v_t$.

- In subcase 2 above, when $v_i \in Q_{i,j}$ and $v_j$ is generated by $Q_{i,j} \cap G_j$, we must only consider the cases when $v_j \notin N(v)$ and, for every $t \in \{1, \dots, \ell\} \setminus \{i, j\}$ with $v_t \in N(v)$, $Q_{i,j} \cap G_t$ must not generate $v_t$. Moreover, if $v_i \in N(v)$, all $Q_{i,j} \cap G_t$ for $t \in \{1, \dots, \ell\} \setminus \{i\}$ must be $v_t$-protected.

- Subcases 3-5 above consider the cases when $v_i$ is generated by $Q_{i,j} \cap G_i$ and $v_j$ is generated by $Q_{i,j} \cap G_j$. In these cases, we must only consider the sets $Q_{i,j}$ such that: either at least two vertices $v_h, v_{h'}$ ($h, h' \in \{1, \dots, \ell\}$) that are generated are neighbors of $v$, in which case, all $Q_{i,j} \cap G_t$ for $t \in \{1, \dots, \ell\}$ must be $v_t$ protected; or a unique vertex $v_h$ ($h \in \{1, \dots, \ell\}$) that is generated is a neighbor of $v$, in which case, all $Q_{i,j} \cap G_t$ for $t \in \{1, \dots, \ell\} \setminus \{h\}$ must be $v_t$-protected; or no generated cut-vertex is adjacent to $v$, in which case there are no other constraint compared with the above case.

**Convexly independent sets of $G$ intersecting $B \setminus \{v_1, \dots, v_\ell\}$ and generating $B$.** We show that computing such a maximum set $Q$ can be done in polynomial time. In particular, this will be taken into account in the computation of $r_v(G, v)$.

* Let us start with those sets $Q$ such that $|Q \cap (B \setminus \{v_1, \dots, v_\ell\})| = 1$. For every $w \in B \setminus \{v_1, \dots, v_\ell\}$, let us consider the set $Q$ such that $Q \cap (B \setminus \{v_1, \dots, v_\ell\}) = \{w\}$ (in particular, for $w = v$, this will be taken into account in the computation of $r_v(G, v)$).

For every $1 \le i \le \ell$ such that $\{v_i, w\} \in E(G)$, we consider the set $Q$ that contains $w$ and contains or generates $v_i$ as follows. Add to $Q$ a convexly independent set $Q_i$ of $G_i$ of size $\max\{r_v(G_i, v_i), r_{\bar{v}h}(G_i, v_i)\}$ ($Q_i$ satisfying the corresponding constraints). Note that such sets have been computed inductively.

Let $T^* \subseteq \{1, \dots, \ell\} \setminus \{i\}$ be such that $t \in T^*$ if and only if $r_{\bar{v}hp}(G_t, v_t) > r_{\bar{v}hp}(G_t, v_t)$. We must find a subset of $\{v_t \mid t \in T^*\} \setminus (N[v_i] \cup N[w])$ that is a stable set in $B \setminus (N[v_i] \cup N[w])$ since this must be a stable set to ensure the convex independence. To compute such a set, compute a maximum weighted stable set $S'$ in the chordal graph induced by $\{v_t \mid t \in T^*\} \setminus (N[v_i] \cup N[w])$ where each vertex $v_t$ has weight $r_{\bar{v}hp}(G_t, v_t) - r_{\bar{v}hp}(G_t, v_t)$. Let $S \subseteq T^*$ be the set of indices
of the vertices in $S'$. Then, for every vertex $v_t$, with $t \in S$, $Q \cap G_t$ must be a set of size $r_{\bar{v}hp}(G_t, v_t)$ (in $G_t$), and for every $t \in \{1, \dots, \ell\} \setminus (\{i\} \cup S)$, the set $Q \cap G_t$ must have size $r_{\bar{v}hp}(G_t, v_t)$.

Similarly to previous items, we will also need to compute such sets that are $v$-protected. The difference is that we will restrict $w$ and $v_i$ not to be in $N[v]$ and the above maximum weight stable sets will be computed among the vertices in $\{v_t | t \in T^*\} \setminus (N[v_i] \cup N[w] \cup N[v])$.

* The other case of this part is when $|Q \cap (B \setminus \{v_1, \dots, v_\ell\})| = 2$. For every $\{w, w'\} \in E(B \setminus \{v_1, \dots, v_\ell\})$, let us consider the set $Q$ such that $Q \cap (B \setminus \{v_1, \dots, v_\ell\}) = \{w, w'\}$. Then, let $T^* \subseteq \{1, \dots, \ell\}$ be such that $t \in T^*$ if and only if $r_{\bar{v}hp}(G_t, v_t) > r_{\bar{v}hp}(G_t, v_t)$.

To complete this set, let us compute a maximum weighted stable set $S'$ of $\{v_t | t \in T^*\} \setminus (N[w] \cup N[w'])$, with $S$ and the weights defined as above. Then, for every vertex $v_t$, $t \in S$, $Q \cap G_t$ must be a set of size $r_{\bar{v}hp}(G_t, v_t)$ (in $G_t$), and for every $t \in \{1, \dots, \ell\} \setminus (\{i\} \cup S)$, the cardinality of $Q \cap G_t$ must be $r_{\bar{v}hp}(G_t, v_t)$.

The sets computed in the previous items will be considered in the computation of $r_v(G, v)$ when $w = v$ or $w' = v$, otherwise, the sets are considered in the computation of $r_{\bar{v}h}(G, v)$. The case when we consider sets that are $v$-protected is similar as above.

**Convexly independent sets of G that do not generate B.** Such a set $Q$ with maximum size can be computed as follows. For all $t \in \{1, \dots, \ell\}$, let $r(t) = \max\{r_{\bar{v}h}(G_t, v_t), r_{\bar{v}h}(G_t, v_t), r_v(G_t, v_t)\}$. Then, let $T^* \subseteq \{1, \dots, \ell\}$ be such that $t \in T^*$ if and only if $r(t) \neq r_{\bar{v}h}(G_t, v_t)$. Let us consider the chordal graph induced by $\{v_t | t \in T^*\} \cup (B \setminus \{v_1, \dots, v_\ell\})$ with weight one for vertices of $B \setminus \{v_1, \dots, v_\ell\}$ and weight $r(t) - r_{\bar{v}h}(G_t, v_t)$ for the vertices $v_t \in \{v_t | t \in T^*\}$. Let $S$ be a maximum weighted stable set of this graph. Then, $Q$ consists of the vertices of $S \setminus \{v_1, \dots, v_\ell\}$, of a convexly independent set $Q_t$ of $G_t$ of size $r(t)$ ($Q_t$ satisfying the corresponding constraints) for every $v_t \in S \setminus \{v_1, \dots, v_\ell\}$ and of a convexly independent set $Q_t$ of $G_t$ of size $r_{\bar{v}h}(G_t, v_t)$ ($Q_t$ satisfying the corresponding constraints) for every $v_t \in \{v_1, \dots, v_\ell\} \setminus S$.

For the computation of $r_{\bar{v}h}(G, v)$, we will need a similar set with the extra restriction that $v$ cannot be chosen. And finally, for the computation of $r_{\bar{v}hp}(G, v)$, we do the same with the extra restriction that $S \cap N[v] = \emptyset$.

**Conclusion of Case 2).** We have computed (in polynomial time) a polynomial number of convexly independent sets, and it can be shown that, for each of the measure $r_v(G, v)$, $r_{\bar{v}h}(G, v)$, $r_{\bar{v}h}(G, v)$, $r_{\bar{v}hp}(G, v)$ and $r_{\bar{v}hp}(G, v)$, at least one set of this size (with the corresponding constraints) belongs to the computed sets. This concludes the inductive part of the algorithm and the proof of the theorem. □

### 3.3. Starlike graphs

A connected graph $G$ is starlike if $V(G)$ can be partitioned into cliques $(K_0, \dots, K_t)$ such that $K_0$ is a maximal clique and for all $l \in \{1, \dots, t\}$ and $v_i, v_j \in K_l$, it holds that

$$K_l \subseteq N[v_i] = N[v_j] \subseteq K_0 \cup K_l.$$

Said differently, $G$ is obtained from the disjoint union of $K_0, \dots, K_t$ by making the join between $K_i$ and some $K_0^i \subseteq K_0$ for every $1 \le i \le t$. If $|K_l| \le k$ for $l \in \{1, \dots, t\}$, then $G$ is $k$-starlike. The 1-starlike graphs are exactly the split graphs. The cliques $K_1, \dots, K_t$ are called the peripheral cliques.
Here we study the rank of starlike graphs. We first need the following straightforward general claim.

**Claim 6.** Let $G$ be any graph with a vertex $v$ with degree 1. Then, a set $S \subseteq V(G \setminus \{v\})$ is convexly independent in $G \setminus \{v\}$ if and only $S \cup \{v\}$ is convexly independent in $G$.

Previous Claim implies that, when computing the rank of a graph for the cycle convexity, vertices of degree 1 can be “ignored”. That is, if $Y$ is the set of degree-1 vertices of a graph $G$, then $\mathrm{rk}(G) = \mathrm{rk}(G \setminus Y) + |Y|$. Therefore, from now on, we assume that the minimum degree $\delta(G)$ of $G$ is at least 2.

Recall that a vertex $v$ is simplicial if $N(v)$ induces a complete subgraph.

**Theorem 18.** Let $G = (K_0, K_1, \dots, K_t)$ be a starlike graph with minimum degree at least 2. Then,

1. $\mathrm{rk}(G) = t + 2$ if $|N(K_i) \cap K_0| = 1$, for all $1 \le i \le t$ and $|V(K_0)| \ge 2$, else

2. $\mathrm{rk}(G) = t + 1$, if $\exists v \in K_0$ such that $\forall u \in K_0, u \ne v, N(v) \cap N(u) \cap V(G) \setminus K_0 = \emptyset$ ($v$ is a cut-vertex or $v$ is a simplicial vertex in $K_0$), else

3. $\mathrm{rk}(G) = t$.

*Proof.* Note that, for every $1 \le i \le t$ such that $|N(K_i) \cap K_0| = 1$, then $|V(K_i)| \ge 2$ since $\delta(G) \ge 2$.

First let us prove the lower bounds. Let $v_i \in V(K_i)$ for every $1 \le i \le t$ and let $S = \{v_1, \dots, v_t\}$. Then, $S$ is convexly independent, showing that $\mathrm{rk}(G) \ge t$. In case 1, let $x \in K_1 \setminus \{v_1\}$ and $y \in K_0 \setminus N(K_1)$, then $S \cup \{x, y\}$ is convexly independent. Finally, in case 2, then $S \cup \{v\}$ is convexly independent.

For the upper bound, let $S'$ be a convexly independent set. First, recall that, by Theorem 4 and Claim 1, $|S' \cap K_i| \le 2$ for every $0 \le i \le t$. Moreover, let $I = \{i \in \{1, \dots, t\} \mid |N(K_i) \cap K_0| \ge 2\}$. Note that,

* for every $i \in I \cup \{0\}$, if there are two vertices $x, y \in S' \cap K_i$, then $\bigcup_{j \in I \cup \{0\}} K_j \subseteq H(\{x, y\})$. Hence, if $I \ne \emptyset$, then either $S'$ contains at most one vertex from each clique $K_i$ with $i \in I \cup \{0\}$; otherwise, it contains at most two vertices in $\bigcup_{j \in I \cup \{0\}} K_j$.

Moreover,

* if there exist $0 \le i < j \le t$ such that $|S' \cap K_i| \ge 2$ and $|S' \cap K_j| \ge 2$, say $x, y \in S' \cap K_i$ and $x', y' \in S' \cap K_j$, first note that if $i = 0$, $(S' \cap K_0) \cap N(K_j) = \emptyset$ since otherwise $S'$ would not be convexly independent. Moreover, because $S'$ is convexly independent it implies that $N(K_i) \cap N(K_j) = \emptyset$ since otherwise $y' \in H(\{x, y, x'\})$. Then $Y = K_i \cup K_j \cup \bigcup_{r \in I \cup \{0\}} K_r \subseteq H(\{x, y, x', y'\})$ and so $S'$ contains 4 vertices in $Y$. Moreover, for every $r' \in W = \{1, \dots, t\} \setminus (I \cup \{i, j\})$ and every vertex $w \in K_{r'}$, $Y \cup K_{r'} \subseteq H(\{x, y, x', y', w\})$, hence, $S'$ contains at most one vertex in any $K_{r'}$, $r' \in W$.

In Case 1 ($I = \emptyset$ and $|K_0| \ge 2$), the second item says that at most 2 cliques contain two vertices of $S'$ and, if such two cliques are peripherical, then $K_0 \cap S' = \emptyset$, and since, all other peripherical cliques contain at most one vertex of $S'$, then $|S'| \le t + 2$. On the other hand, if $|K_0 \cap S'| = 2$, then every peripherical clique contains at most one vertex of $S'$ (since $H(S' \cap K_0) = K_0$). Therefore, in Case 1, $|S'| \le t + 2$.

Now, let us consider the Case 2 ($I \ne \emptyset$ and there is a cut vertex or a simplicial vertex in $K_0$) and let $s = t - |I| < t$. For the purpose of contradiction, assume that $|S'| \ge t + 2$. Hence, there exists
0 ≤ i ≤ t, |S' ∩ Kᵢ| = 2. If i ∈ I ∪ {0}, by the first item, S' has at most two vertices in ⋃ⱼ∈I∪{0} Kⱼ (and S' has at most one vertex per clique Kᵣ, with r /∈ I ∪ {0}, since K₀ ⊆ H(S' ∩ (∪ⱼ∈I∪{0} Kⱼ)) and so |S'| ≤ s + 2 < t + 2, a contradiction. Hence, i /∈ I ∪ {0}. If there exists another j /∈ I ∪ {0}, j ≠ i such that |S' ∩ Kⱼ| = 2, then by second item, S' contains 4 vertices in Kᵢ ∪ Kⱼ ∪ ⋃ₜ∈I∪{0} Kₜ and at most one vertex in the other cliques, i.e., |S'| ≤ 4 + s − 2 < t + 2, again a contradiction. Therefore, there exists a unique i /∈ I ∪ {0} with |S' ∩ Kᵢ| = 2. If |S' ∩ K₀| ≠ ∅, then Kᵣ ⊆ H(S' ∩ (Kᵢ ∪ K₀)) for every r ∈ I, and so S' ∩ Kᵣ = ∅ and |S'| ≤ s + 2 < t + 1, a contradiction. Hence, S' ∩ K₀ = ∅ and, since all other cliques (but Kᵢ) contain at most one vertex of S', then |S'| ≤ t + 1.

In Case 3 ($I = \{1, \dots, t\}$ and there are no simplicial vertices in $K_0$), if $S' \cap K_0 = \emptyset$, then $|S'| \le t$ by Item 1. Otherwise, let $v \in K_0 \cap S'$. Since $v$ is not simplicial (otherwise we would be in case 2), let $1 \le i \le t$ such that $v \in N(K_i)$. Let $w \in K_i \cup K_0 \setminus \{v\}$, then $H(\{v, w\}) = V(G)$ (since $v$ is not a cut-vertex). Hence, if $|S'| > 2$, it contains at most one vertex in $K_0 \cup K_i$ and, by Item 1, in Case 3, $|S'| \le t$. □

### 3.4. $(q, q-4)$-graphs

A graph $G$ is $(q, q-4)$ for some integer $q \ge 4$ if every subset with at most $q$ vertices induces at most $q-4$ $P_4$'s [37]. Observe that the cographs are exactly the $(4, 0)$-graphs and the $P_4$-sparse [38] are the $(5, 1)$-graphs.

A graph $G$ is a $(R, K, S)$-spider if $V(G)$ can be partitioned into the sets $K$, $S$ and $R$, where $R$ may be empty, such that:

* each vertex in $R$ is adjacent to every vertex in $K$, and no vertex in $R$ is adjacent to any vertex in $S$;

* $|K| = |S| \ge 2$;

* $K$ is a clique, $S$ is a stable set;

* there is a bijection $f: S \to K$ such that either $N(s) = \{f(s)\}$ for every $s \in S$ (in which case we say that $G$ is a *thin spider*), or $N(s) = K \setminus \{f(s)\}$ for every $s \in S$. In this case, we say that $G$ is a *thick spider*.

In other words, in a thin spider the adjacencies between $S$ and $K$ induce a matching, while it is an anti-matching in a thick spider.

The subgraph $G[R]$ is called the head of the spider.

**Lemma 19.** Let $G$ be a $(R, K, S)$-spider. Therefore,

$$ \mathrm{rk}(G) = \begin{cases} \alpha(G[R]) + |S|, & \text{if } G \text{ is a thick spider;} \\ \max\{\alpha(G[R]), 2\} + |S|, & \text{if } G \text{ is a thin spider} \end{cases} $$

*Proof.* Let $G$ be any spider. Let $X$ be any stable set in $G[R]$, then $X \cup S$ is stable (since $K$ separates $R$ and $S$) and so $X \cup S$ is convexly independent and $\alpha(G[R]) + |S| \le \mathrm{rk}(G)$.

Suppose $G$ is a thick spider (we may assume that $|S| \ge 3$ since the case $|S| = 2$ can be seen as a thin spider). Let $\{u, v\} \in E(G[R \cup K])$ be any edge of $G[R \cup K]$. Then $R \cup K \subseteq H(\{u, v\})$ (because $K$ is a clique of order at least 3 and there is a join between $R$ and $K$). Moreover, since $|S| \ge 3$ and we are looking at a thick spider, $S \subseteq H(K)$. Therefore, any convexly independent set
of $G$ containing an edge of $G[R \cup K]$ has size 2. Hence, any convexly independent set of $G$ either contains a single vertex of $K$ and a subset of $S$, or consists of a stable set of $R$ union a subset of $S$. Hence, $\alpha(G[R]) + |S| \ge \mathrm{rk}(G)$.

In the case of a thin spider, the difference is that $S \cap H(K) = \emptyset$ and $H(S) = S$, and so a set $X$ consisting of an edge of $G[R \cup K]$ union $S$ is also convexly independent. Hence, any convexly independent set of $G$ either contains a single vertex of $K$ and a subset of $S$, or consists of a stable set of $R$ union a subset of $S$, or consists of an edge of $G[R \cup K]$ union $S$. Hence, $\max\{2, \alpha(G[R])\} + |S| = \mathrm{rk}(G)$. $\square$

A graph $G = (R, K, S, E)$ is a $q$-pseudo-spider if $V(G)$ can be partitioned into sets $R, K$ and $S$. Moreover, the subgraph $G[R \cup K]$ is the join $R \oplus K$; the set $K$ separates $R$ from $S$, i.e. any path from a vertex in $S$ to a vertex in $R$ contains a vertex in $K$, and $|K \cup S| \le q$.

**Theorem 20** ([39]). Let $q \ge 4$ be fixed. If $G$ is a $(q, q-4)$-graph, then one of the following holds:

* $G$ is a single vertex;

* $G = G_1 \cup G_2$ is the disjoint union of two $(q, q-4)$-graphs $G_1$ and $G_2$;

* $G = G_1 \oplus G_2$ is the join of two $(q, q-4)$-graphs $G_1$ and $G_2$;

* $G$ is a $(R, K, S)$-spider where $G[R]$ is a $(q, q-4)$-graph if $R \ne \emptyset$;

* $G$ is a $q$-pseudo-spider $(R, K, S, E)$ where $G[R]$ is a $(q, q-4)$-graph if $R \ne \emptyset$.

The Theorem 20 yields a tree structure $T(G)$ (referred to as the *primeval tree*) that encodes the Primeval Decomposition of a $(q, q-4)$-graph $G$. The graph $T(G)$ is a rooted binary tree in which each node $v$ corresponds to an induced $(q, q-4)$-subgraph $G_v$ of $G$, and the root corresponds to the graph $G$ itself. Furthermore, the subgraphs associated with the leaves of $T(G)$ induce a partition of $V(G)$; that is, the collection $\{V(G_\ell)\}_{\ell \text{ leaf of } T(G)}$ forms a partition of the vertex set of $G$.

Each leaf $\ell$ of $T(G)$ corresponds either to a spider $(\emptyset, K, S)$ or to a subgraph with at most $q$ vertices. Internal nodes are labeled according to one of the last four cases described in Theorem 20. More precisely, let $v$ be an internal node of $T(G)$ with children $u$ and $w$. Then:

* $v$ is a *parallel node* if $G_v = G_u \cup G_w$;

* $v$ is a *series node* if $G_v = G_u \oplus G_w$;

* $v$ is a *spider node* if $u$ is a leaf with $G_u$ being a spider $(\emptyset, K, S)$, and $G_v$ is the spider $(R, K, S)$, where $G_v[R] = G_w$ and $G_v[K \cup S] = G_u$.

This tree can be obtained in linear time [40].

**Lemma 21.** Let $q \ge 4$ be fixed. If $G$ is a $q$-pseudo-spider $(R, K, S, E)$ where $G[R]$ is a $(q, q-4)$-graph if $R \ne \emptyset$, then $\mathrm{rk}(G)$ can be computed in time $\tilde{O}(2^q)$ where $\tilde{O}$ hides a polynomial factor in $|V(G)|$.

*Proof.* Let $G$ be a $q$-pseudo-spider $(R, K, S, E)$.

Let $X$ be a convexly independent set of $G$. There are several cases to be considered: either 1) $X \cap R = \emptyset$, or 2) $X \cap R \ne \emptyset$. In the latter case, $X' = X \setminus S$ is convexly independent in $R \oplus K$ (by Claim 1) and so, by the proof of Lemma 5: either 2a) $|X'| \le 3$ or 2b) $X'$ is any stable set
of $R$ (plus possibly the unique vertex of $K$ only if $|K| = 1$), or 2c) $|R| = 1$ (in this last case, $|V(G)| \le q + 1$, and the result follows easily).

Therefore, our algorithm proceeds by exhaustive search by checking all subsets with at most 3 vertices in $R \cup K$ (testing if they are convexly independent and keeping a largest one), which can be done in time $\tilde{O}(2^q)$ (since $|S| \le q$) and covers cases 1) and 2a). Then, the algorithm computes a maximum stable set of $R$ (which can be done in polynomial time since $R$ is a $(q, q-4)$-graph [39]) and tries to add to it all possible subsets of $S$ (possibly plus the unique vertex of $K$, if $|K| = 1$). This takes again a time $\tilde{O}(2^q)$ and covers the case 2b).

Finally, the algorithm returns a maximum convexly independent set among the ones it has computed. □

**Theorem 22.** Let $G$ a $(q, q-4)$-graph with fixed $q \ge 4$, rk$(G)$ can be computed in polynomial time.

*Proof.* Let us first build in polynomial time a primeval decomposition $\mathcal{T}$ (where each node corresponds to a case of Theorem 20) of $G$. Then, a bottom-up dynamic programming algorithm using the above results can be used: the case of disjoint union and join is handled by Lemma 5, the case of spiders is done using Lemma 19 and pseudo-spiders are considered using Lemma 21. □

# 4. FPT algorithms

This section is devoted to FPT algorithms for computing the rank, parameterized by neighbourhood diversity and treewidth.

## 4.1. FPT algorithm by neighborhood diversity

Two vertices $u, v$ of a graph $G$ have the same type if $N(u) \setminus \{v\} = N(v) \setminus \{u\}$. Two vertices with the same type are true twins (resp. false twins) if they are adjacent (resp. non-adjacent).

The neighborhood diversity of a graph $G$, denoted by nd$(G)$, as defined by Lampis [41], is the minimum integer $k$ such that $V(G)$ can be partitioned into $k$ sets such that all the vertices in each set have the same type. Note that the property of having the same type is an equivalence relation. Observe that the minimum such integer $k$ can be computed in cubic time by iteratively checking the neighborhood of pairs of vertices of the input graph and creating the partition [41].

Thus, a graph $G = (V, E)$ has neighborhood diversity at most $k$ if $V$ can be partitioned into $k$ sets $\{V_1, \cdots, V_k\}$ such that, for each $1 \le i \le k$, $V_i$ either induces a complete graph or a stable set and, for every $1 \le i < j \le k$, either there are no edges between the vertices of $V_i$ and $V_j$, or all edges between the two sets are in $E$. In other words, for each $1 \le i \le k$, all vertices of $V_i$ are true twins, or they are all false twins.

**Lemma 23.** Let $S \subseteq V(G)$ be a set of vertices, and let $C \subseteq S$ be a subset of false twins with $|C| \ge 4$. Let $C' \subseteq C$ be a subset of four pairwise distinct vertices. Then $S$ is convexly independent if and only if $S' = (S \setminus C) \cup C'$ is convexly independent.

*Proof.* Assume first that $S$ is convexly independent. Since $S' \subseteq S$, the convex independence of $S'$ follows directly from Claim 1.

On the other hand, assume $S'$ is convexly independent, but suppose for the sake of contradiction that $S$ is not. Then there exists a vertex $z \in S$ such that $z \in H(S \setminus \{z\})$. This implies the existence of an induced cycle $K$ such that $z \in K$ and $K \setminus \{z\} \subseteq H(S \setminus \{z\})$.
A known property of a set of false twins, $C$, is that any induced cycle $K$ can contain at most two vertices of $C$. In particular, take two vertices $c, d \in C'$, the following holds: if $x \in H(K)$ then $x \in H((K \setminus C) \cup \{c, d\})$, since substituting vertices from $C$ with vertices from $\{c, d\}$ preserves adjacency. Let $K_C = K \cap C$, for the reason just presented, $|K_C| \le 2$. Then we consider two cases.

**Case 1:** $z \notin C$. In this case, $z \in S \setminus C$, which means $z \in S'$. Let $K' = (K \setminus K_C) \cup K'_C$, where $K'_C$ is a set of $|K_C|$ distinct vertices chosen from $C' \setminus \{c, d\}$. This is possible because $|C'| = 4$, $|K_C| \le 2$, and all vertices in $C$ have the same neighborhood. Therefore, $K'$ is also an induced cycle. By construction, $z \in K'$ and $K' \setminus \{z\} = (K \setminus C \cup \{z\}) \cup K'_C$. The set $K'_C$ is a subset of $C'$ and $K \setminus C \cup \{z\} \subseteq H((S \setminus C) \cup \{c, d\})$. Thus, $K' \setminus \{z\} \subseteq H((S \setminus C \cup \{z\}) \cup C') = H(S' \setminus \{z\})$. Furthermore, since $z \in K'$ this implies that $z \in H(S' \setminus \{z\})$, which contradicts our assumption that $S'$ is convexly independent.

**Case 2:** $z \in C$. Let $K_C = (K \setminus \{z\}) \cap C$. Since $z \in K \cap C$ and at most two vertices from $C$ can belong to the same induced cycle, we have $|K_C| \le 1$. Suppose $y \in K_C$ if this intersection is non-empty. Pick a new vertex $b \in C' \setminus \{c, d\}$. Let's replace $z$ with $b \in C'$. If $y \in K_C$, we replace $y$ with another vertex $a \in C' \setminus \{b, c, d\}$. Let $K' = (K \setminus \{z, y\}) \cup \{b, a\}$ (if $y$ exists) or $K' = (K \setminus \{z\}) \cup \{b\}$ (if $K_C$ is empty). As before, $K'$ is an induced cycle. By construction, $b \in K'$ and $K' \setminus \{b\} = (K \setminus \{z, y\}) \cup \{a\}$ or $K' \setminus \{b\} = K \setminus \{z, y\}$. The vertices in $K \setminus \{z, y\}$ belong to $H((S \setminus C) \cup \{c, d\})$. The vertex $a$ (if it exists) belongs to $C'$. Therefore, all vertices in $K' \setminus \{b\}$ are contained in $H((S \setminus C) \cup C') = H(S')$. Since $b$ is distinct from these vertices, they are all in $S' \setminus \{b\}$. We have found a vertex $b \in S'$ and an induced cycle $K'$ containing $b$ such that $K' \setminus \{b\} \subseteq H(S' \setminus \{b\})$. This implies $b \in H(S' \setminus \{b\})$, which contradicts the convex independence of $S'$. $\square$

**Theorem 24.** The RANK problem can be solved in $O(5^k k^3 + n^3)$-time if the input graph $G$ has $n$ vertices and neighborhood diversity $nd(G) = k$.

*Proof.* Let $\{V_1, \dots, V_k\}$ be the neighborhood diversity partition of the graph $G$ which can be computed in $O(n^3)$ time. Each part $V_i$ induces either a clique or an independent set.

Let us design a brute force algorithm to compute a maximum convexly independent set. The key point is that this algorithm will have to consider at most two vertices in each $V_i$ inducing a clique and at most four vertices in each $V_i$ inducing a stable set.

Indeed, let $X$ be any convexly independent set of $G$. Since $X$ is acyclic, for every $1 \le i \le k$ such that $V_i$ induces a clique, then $|X \cap V_i| \le 2$. Moreover, for every $v \in X \cap V_i$ and $u \in V_i \setminus X$, $X \cup \{u\} \setminus \{v\}$ is also convexly independent since $u$ and $v$ are twins. Moreover, let $1 \le i \le k$ such that $V_i$ induces a stable set, by Lemma 23, if $|X \cap V_i| \ge 4$, then $X \cup V_i$ is convexly independent.

The above discussion actually shows that the following algorithm is correct. Let $res$ be a variable that will contain the result, initially the empty set.

The algorithm considers each vector $(s_1, s_2, \dots, s_k)$ where, for every $1 \le i \le k$, $s_i \in \{0, 1, 2\}$ if $V_i$ induces a clique, and $s_i \in \{0, 1, 2, 3, 4\}$ if $V_i$ induces a stable set. For each such a vector $(s_1, s_2, \dots, s_k)$, let $X$ be any set with $|X \cap V_i| = s_i$ for every $1 \le i \le k$ (so $|X| \le 4k$) and check whether $X$ is convexly independent in time $O(k^3)$. If $X$ is convexly independent, let $I = \{1 \le i \le k \mid V_i$ induces a stable set and $s_i = 4\}$ and let $X' = X \cup \bigcup_{i \in I} V_i$. If $|X'| \ge |res|$, then the variable $res$ becomes $X'$. Eventually, $res$ is a maximum convexly independent set of $G$.

The total time complexity is the sum of the initial partitioning ($O(n^3)$) and the brute-force check of all configurations ($O(5^k k^3)$). $\square$
### 4.2. FPT algorithm by treewidth

Note that the class of complete graphs has bounded neighborhood diversity and unbounded treewidth, while in the class of paths the converse occurs. In this section, we prove that the RANK problem may be formulated using an MSOL formula and so, by Courcelle's theorem [42], it is FPT parameterized by the treewidth of the input graph plus the value of the solution.

**Theorem 25.** Given a graph G and a positive integer k, deciding whether rk(G) ≥ k is FPT parameterized by $tw(G) + k$.

*Proof.* Let $(G, k)$ be an input to the RANK problem. According to Courcelle's Theorem [42], it suffices to express in Monadic Second Order Logic (MSOL) a formula that determines whether a subset $S \subseteq V(G)$ is convexly independent.

The ideas in this proof can be partly found in previous works in the literature, e.g. [43, 12, 30]. We use the notation $X \subseteq Y$ to represent the standard MSOL formula $\forall x(x \in X \Rightarrow x \in Y)$, and let V denote the vertex set $V(G)$.

Recall that it suffices to verify the existence of a set $S \subseteq V(G)$ with exactly k vertices such that S is convexly independent to determine whether rk(G) ≥ k. We can confirm this using the formula:

$$rk(k) := \exists S \subseteq V (\text{ExctK}(S, k) \land \text{CvxlyInd}(S))$$

We verify that S contains exactly k vertices using:

$$\text{ExctK}(S, k) := \exists x_1, x_2, \dots, x_k \in V \left( \left( \bigwedge_{i=1}^{k} x_i \in S \right) \land \left( \bigwedge_{i \neq j} x_i \neq x_j \right) \land \left( \forall y \in S \left( \bigvee_{i=1}^{k} y = x_i \right) \right) \right)$$

The convexly independent property is checked as:

$$\text{CvxlyInd}(S) := \forall z \in S (\forall X \subseteq V (\text{ConvexHull}(X, S \setminus \{z\}) \Rightarrow z \notin X))$$

A set X is the convex hull of a set T if and only if:

$$\text{ConvexHull}(X, T) := \text{Convex}(X) \land ((X = T) \lor (\forall Z \subseteq V ((T \subseteq Z \land Z \subset X) \Rightarrow \neg \text{Convex}(Z)))))$$

Convexity of a set is determined by:

$$\text{Convex}(X) := \forall v \in V \setminus X (\neg (\text{TwoAdjSmComp}(v, X)))$$

We check whether a vertex v has two neighbors u and w in the same connected component of the subgraph induced by a set X, we use:

$$\text{TwoAdjSmComp}(v, X) := \exists u, w \in X (u \neq w \land \text{adj}(v, u) \land \text{adj}(v, w) \land \text{Connected}(u, w, X))$$

Finally, connectivity between two vertices in $G[X]$ can be expressed as:

$$\text{Connected}(u, w, X) := u \in X \land w \in X \land \forall Y \subseteq X (u \in Y \land w \notin Y \Rightarrow \exists r \in Y \land \exists s \notin Y (\text{adj}(r, s)))$$

Therefore, we can write a MSOL formula to express that a set S is convexly independent and has exactly k vertices, whose correctness can be easily verified. □
**5. Final Remarks**

We conclude by discussing some open problems and directions for future work.

In Section 2, we proved in Theorem 8 that the RANK problem is NP-complete even when re-
stricted to bipartite graphs. Since the reduction used is not a parameterized one, and given that the
SET PACKING problem is known to be W[1]-hard when parameterized by the size of the solution, a
natural question arises:

**Problem 26.** Given a bipartite graph $G$ and a positive integer $k$, is it FPT to decide whether $rk(G) \ge k$, when parameterized by $k$?

In Section 4.1, we present an FPT algorithm to solve the RANK problem parameterized by the neighborhood diversity of the input graph. Recall that $S \subseteq V(G)$ is a vertex cover of $G$ if each edge of $G$ has an endpoint in $S$. Let $vc(G)$ be the minimum cardinality of a vertex cover of $G$. If a graph $G$ has a vertex cover $S$ of size $k$, $V(G)$ can be easily partitioned into at most $2^k + k$ equivalence classes of types, thus implying that, for any graph $G$, $nd(G) \le 2^{vc(G)} + vc(G)$. Consequently, from Theorem 24 we obtain the RANK problem parameterized by the vertex cover is FPT, but such an algorithm will be double exponential in $vc(G)$.

It would be interesting to have a simple reduction rule to remove true twin vertices, as we
succeeded in doing for false twin vertices in Lemma 23. In this case, Theorem 24 could be presented
as a kernelization algorithm. A natural question is:

**Problem 27.** Does the RANK problem admit a polynomial kernel when parameterized by the vertex cover of the input graph?

A possibility to negatively answer Problem 27 would be to use OR-cross-compositions [2]. In this direction, an attentive reader could observe that Lemma 5 provides a proof that, if $G$ is the graph obtained by joining the graphs $G = G_1 \oplus \dots \oplus G_t$ corresponding to $t$ instances $(G_1, k), \dots, (G_t, k)$ of the INDEPENDENT SET problem, then $rk(G) \ge k$ if and only if $\max_{1 \le i \le t} rk(G_i) \ge k$. However, such an idea does not work when the parameter is $vc(G)$.

Since the complement $\bar{S} = V(G) \setminus S$ of a vertex cover $S$ in a graph $G$ is an independent set, actually, there is a convexly independent set with $|V(G)| - vc(G)$ vertices. The question is actually how to improve such a bound.

In this context, another natural question would be to consider the dual version of the RANK problem:

**Problem 28.** Given a graph $G$ and a positive integer $k$, is deciding whether $rk(G) \ge |V(G)| - k$ an FPT problem, when the parameter is $k$?

Although the Helly and Radon numbers were not explicitly addressed in this work, they are
classical parameters in the theory of convexity spaces. The Helly number measures how convex
sets overlap, while the Radon number captures how point sets can be separated. Together with the
rank, these parameters provide insight into the structure of convexity spaces, particularly in terms
of dimensionality and separability. It is well known [44] that the rank provides an upper bound for
both the Helly and Radon numbers in any convexity structure. Therefore, our results can also be
leveraged to derive bounds on these classical parameters in the context of cycle convexity, suggesting
promising directions for future investigation.
Acknowledgments

This work is partly funded by CNPq (Brazil) projects 313153/2021-3 and 404613/2023-3, by Inria
Associated Team CANOE and by project CAPES-Cofecub 49587PE (Brazil-France). Caroline Silva
was supported by FAPESP Proc. 2023/16755-2.

References

[1] J.A. Bondy and U.S.R. Murty. Graph theory. In *Graduate Texts in Mathematics*, volume 244, page 663. Springer, 2008.

[2] M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. *Parameterized Algorithms*. Springer, 1st edition, 2015.

[3] V.W Bryant and R.J Webster. Convexity spaces. I. the basic properties. *Journal of Mathematical Analysis and Applications*, 37(1):206-213, 1972.

[4] Júlio Araújo, Mitre C. Dourado, Fábio Protti, and Rudini M. Sampaio. *Introduction to Graph Convexity - An Algorithmic Approach*. Springer Cham, 2025.

[5] F. Harary and J. Nieminen. Convexity in graphs. *J. Differ. Geom.*, 16(2):185-190, 1981.

[6] I.M. Pelayo. *Geodesic Convexity in Graphs*. Springer, 2013.

[7] Paul Erdős. Some remarks on simple tournaments. *Algebra Universalis*, 2:238–245, 1972.

[8] Carmen C. Centeno, Mitre C. Dourado, and Jayme L. Szwarcfiter. On the convexity of paths of length two in undirected graphs. *Electronic Notes in Discrete Mathematics*, 32:11–18, 2009.

[9] R.T. Araújo, R.S. Sampaio, V.F. dos Santos, and J.L. Szwarcfiter. The convexity of induced paths of order three and applications: complexity aspects. *Discrete Appl. Math.*, 237:33–42, 2018.

[10] R Jamison. A perspective on abstract convexity: Classifying alignments by varieties, convexity and related combinational geometry. In *Proc. Univ. of Oklahoma Conf. Marcel Dekker, Inc New York, 1982.*

[11] Pierre Duchet. Convex sets in graphs, II. Minimal path convexity. *Journal of Combinatorial Theory, Series B*, 44(3):307–316, 1988.

[12] J. Araujo, G. Ducoffe, N. Nisse, and K. Suchan. On interval number in cycle convexity. *Discrete Math. Theor. Comput. Sci.*, 20(1):1–28, 2018.

[13] Júlio Araújo, Victor Campos, Darlan Girão, João Nogueira, António Salgueiro, and Ana Silva. Cycle convexity and the tunnel number of links, 2020.

[14] J. Araujo, V. Campos, D. Girão, J. Nogueira, A. Salgueiro, and A. Silva. On the hull number on cycle convexity of graphs. *Information Processing Letters*, 183:106420, 2024.

[15] Manuel, Paul, and Sandi Klavzar. A general position problem in graph theory. *Bulletin of the Australian Mathematical Society*, 98(2):177–187, 2018.
[16] Paul Manuel and Sandi Klavžar. The graph theory general position problem on some interconnection networks. *Fundamenta Informaticae*, 163(4):339–350, 2018.

[17] Paul Erdös, Michael Saks, and Vera T Sós. Maximum induced trees in graphs. *Journal of Combinatorial Theory, Series B*, 41(1):61–79, 1986.

[18] Noga Alon. Problems and results in extremal combinatorics—i. *Discrete Mathematics*, 273(1):31–53, 2003.

[19] Jin Akiyama and Mamoru Watanabe. Maximum induced forests of planar graphs. *Graphs and Combinatorics*, 3(1):201–202, 1987.

[20] François Dross, Mickael Montassier, and Alexandre Pinlou. Large induced forests in planar graphs with girth 4. *Discrete Applied Mathematics*, 254:96–106, 2019.

[21] Sheng Bau, Lowell Beineke, Z. Liu, G.-M Du, and R. Vandell. Decycling cubes and grids. *Utilitas Mathematica*, 59, 05 2001.

[22] Riccardo Focardi, Flaminia L. Luccio, and David Peleg. Feedback vertex set in hypercubes. *Information Processing Letters*, 76(1):1–5, 2000.

[23] Karen Gunderson, Karen Meagher, Joy Morris, and Venkata Raghu Tej Pantangi. Induced forests in some distance-regular graphs. *Discrete Applied Mathematics*, 346:290–300, 2024.

[24] Dudeney and Henry. *Amusements in mathematics*, volume 473. Courier Corporation, 1958.

[25] Achim Flammenkamp. Progress in the no-three-in-line problem, ii. *Journal of Combinatorial Theory, Series A*, 81(1):108–113, 1998.

[26] Paul Manuel and Sandi Klavžar. A general position problem in graph theory. *Bulletin of the Australian Mathematical Society*, 98(2):177–187, 2018.

[27] Julio Araujo, Mitre C. Dourado, Fábio Protti, and Rudini Sampaio. The iteration time and the general position number in graph convexities. *Applied Mathematics and Computation*, 487:129084, 2025.

[28] Robert Jamison. Partition numbers for trees and ordered sets. *Pacific Journal of Mathematics*, 96, 09 1981.

[29] Igor Ramos, Vinicius dos Santos, and Jayme Szwarcfiter. Complexity aspects of the computation of the rank of a graph. *Discrete Mathematics & Theoretical Computer Science*, 16, 2014.

[30] Mamadou Kanté, Rudini Sampaio, Vinicius dos Santos, and Jayme Szwarcfiter. On the geodetic rank of a graph. *Journal of Combinatorics*, 8:323–340, 01 2017.

[31] Bijo S. Anand, Arun Anil, Manoj Changat, Revathy S. Nair, and Prasanth G. Narasimha-Shenoi. Helly number, radon number and rank in $\Delta$-convexity on graphs. In Daya Gaur and Rogers Mathew, editors, *Algorithms and Discrete Applied Mathematics*, pages 292–306, Cham, 2025. Springer Nature Switzerland.
[32] D.G. Corneil, H. Lerchs, and L.Stewart Burlingham. Complement reducible graphs. *Discrete Applied Mathematics*, 3(3):163-174, 1981.

[33] D. G. Corneil, Y. Perl, and L. K. Stewart. A linear recognition algorithm for cographs. *SIAM Journal on Computing*, 14(4):926-934, 1985.

[34] Richard Karp. Reducibility among combinatorial problems. In *Proceedings of a Symposium on the Complexity of Computer Computations*, volume 40, pages 85-103, 01 1972.

[35] Bijo S. Anand, Arun Anil, Manoj Changat, Mitre C. Dourado, and Sabeer S. Ramla. Computing the hull number in $\Delta$-convexity. *Theoretical Computer Science*, 844:217-226, 2020.

[36] Andras Frank. Some polynomial algorithms for certain graphs and hypergraphs. *Proceedings of the Fifth British Combinatorial Conference*, 01 1975.

[37] Luitpold Babel and Stephan Olariu. On the structure of graphs with few p4s. *Discrete Applied Mathematics*, 84(1):1-13, 1998.

[38] Beverly Jamison and Stephan Olariu. Linear time optimization algorithms for p4-sparse graphs. *Discrete Applied Mathematics*, 61(2):155-175, 1995.

[39] Luitpold Babel and Stephan Olariu. On the isomorphism of graphs with few p4s. In Manfred Nagl, editor, *Graph-Theoretic Concepts in Computer Science*, pages 24-36, Berlin, Heidelberg, 1995. Springer Berlin Heidelberg.

[40] Luitpold Babel and Stephan Olariu. On the p-connectedness of graphs – a survey. *Discrete Applied Mathematics*, 95(1):11-33, 1999.

[41] Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. *Algorithmica*, 64(1):19-37, 2012.

[42] B. Courcelle and M. Mosbah. Monadic second-order evaluations on tree-decomposable graphs. *Theoretical Computer Science*, 109(1):49-82, 1993.

[43] Mamadou Moustapha Kanté and Lhouari Nourine. Polynomial time algorithms for computing a minimum hull set in distance-hereditary and chordal graphs. *SIAM Journal on Discrete Mathematics*, 30(1):311-326, 2016.

[44] M. L. J. van de Vel. *Theory of Convex Structures*, volume 50. North Holland, Amsterdam, 1st edition, 1993.