The Hull Number in the Convexity of Induced Paths of Order 3

Abstract

A set S of vertices of a graph G is $P^*_3$-convex if there is no vertex outside S having two non-adjacent neighbors in S. The $P^*_3$-convex hull of S is the minimum $P^*_3$-convex set containing S. If the $P^*_3$-convex hull of S is V(G), then S is a $P^*_3$-hull set. The minimum size of a $P^*_3$-hull set is the $P^*_3$-hull number of G. In this paper, we show that the problem of deciding whether the $P^*_3$-hull number of a chordal graph is at most k is NP-complete and present a linear-time algorithm to determine this parameter and provide a minimum $P^*_3$-hull set for unit interval graphs.

1 Introduction

We consider finite, undirected, and simple graphs. The path with k vertices is denoted by $P_k$ and an induced path is a path having no chords. Given a set S of vertices of a graph G, the interval of Sin the convexity of induced paths of order 3, also known as the $P^*_3$convexity, is the set $[S]^*_3 = S \cup \{u : u$ belongs to an induced $P_3$ between two vertices of $S\}$. The set S is $P^*_3$-convex if $S = [S]^*_3$ and is $P^*_3$-concave if $V(G) \setminus S$ is $P^*_3$-convex. The $P^*_3$-convex hull of S is the minimum $P^*_3$-convex set containing S and it is denoted by $\langle S \rangle ^*_3$. If $\langle S \rangle ^*_3 = V(G)$, then S is a $P^*_3$-hull set. The minimum size of a $P^*_3$-hull set is the $P^*_3$-hull number $h^*_3(G)$of G.

Recently, the $P^*_3$ convexity has attracted attention as an alternative to other quite known convexities with different behavior despite a similar definition. It is particularly interesting in spreading dynamics which forbid the same influence by two neighbors to get spread to a common neighbor. For instance, in [4], it is shown that the problem of deciding whether the $P^*_3$-hull number of a bipartite graph is at most k is NP-complete, while polynomial-time algorithms for determining this parameter for $P_4$-sparse graphs and cographs are presented. Apart from these results very little is known, as results of quite similarly defined well-known convexities do not help, since the proofs depend on the existence of longer shortest paths or a non-induced $P_3$.

In the well-known geodetic convexity, the geodetic interval of S is $[S]_g = S \cup \{u : u$ belongs to some shortest path between two vertices of $S\}$. The terms geodesically convex, geodesically concave, geodetic convex hull $\langle S \rangle _g$, geodetic hull set, and geodetic hull number $h_g(G)$ are defined in a similar way to the $P^*_3$ convexity. The literature concerning the geodetic hull number is large. It is known that this problem is NP-complete for chordal graphs [5], $P_9$-free graphs [10], and partial cubes [1]; and that one can find a minimum geodetic hull set in polynomial time if the input graph is unit interval [9], $(q,q-4)$-graph [2], cobipartite [2], cactus [2], (paw, $P_5)$-free [10], $(C_3, \ldots , C_{k-2}, P_k)$-free [10], $P_5$-free bipartite [3], or planar partial cube quadrangulation [1]. However, as already remarked, though an induced path of order 3 is a shortest path of length 2 between a pair of nodes, those results do not directly apply to the $P^*_3$ convexity due to the use of longer shortest paths in proofs.

Unlike the $P^*_3$ convexity, the $P_3$convexity considers all paths of order 3. In this convexity, also known as irreversible 2-conversion, the problem of computing the hull number is APX-hard for bipartite graphs with maximum degree at most 4 and NP-complete for planar graphs with maximum degree at most 4 [7, 15], and can be found in polynomial time for chordal graphs [6] as well as for cubic or subcubic graphs [15]. Finally, in the convexity that considers all induced paths, the monophonic convexity, the hull number can be computed in polynomial time for any graph [11].

The main result of this paper is a linear-time algorithm to determine both the $P^*_3$-hull number and a minimum $P^*_3$-hull set of a unit interval graph (Sect. 2). We point out that Theorem 1 is not only an explicit formula for the $P^*_3$-hull number $h^*_3(G)$ but also an almost explicit one for the minimum $P^*_3$-hull set, since one needs to compute the necessary labels before. We also show that the problem of deciding whether this parameter is at most k for a chordal graph is NP-complete (Sect. 3). Remember that unit interval graphs have a variety of applications in operations research, including resource allocation problems in scheduling [13] and in genetic modeling such as DNA mapping in bioinformatics [14], where an overall agreement (on a value, a signal, a failure, a disease, a characteristic, etc.) might get forced by a minimum key set under some convexity such as the $P^*_3$.

We conclude this section giving some definitions. The distance between vertices u and v is denoted by d(u, v) and the neighborhood of a vertex v is denoted by N(v). The set $\{1, \ldots , k\}$ for an integer $k \ge 1$ is denoted by [k]. A subgraph of G induced by vertex set S is denoted by G[S]. A vertex u is simplicial if its neighborhood induces a complete graph. Note that every $P^*_3$-hull set contains all simplicial vertices and at least one vertex of each $P^*_3$-concave set of the graph. Given an ordering $\alpha = (v_1, \ldots , v_n)$ of V(G) and a set $I \subseteq [n]$, the subordering $\alpha ' = (v_{i_1}, \ldots , v_{i_{|I|}})$of $\alpha$induced by I is the ordering of the set $\{v_{i_j}: {i_j} \in I\} \subseteq V(G)$ such that $v_{i_j}$ appears before $v_{i_k}$ if and only if $i_j < i_k$. If $I = [j] \setminus [i-1]$ for $0 \le i < j \le n$, then the subordering of $\alpha$ induced by I is denoted by $\alpha _{i,j}$.

2 Unit Interval Graphs

A unit interval graph G is the intersection graph of a collection of intervals of the same size on the real line. Since one can assume that all left endpoints of the intervals of such a collection are distinct, a canonical ordering $\varGamma = (v_1, v_2, \ldots , v_n)$of V(G) is defined as the one such that $i < j$ if and only if the left endpoint of the interval of $v_i$ is smaller than the left endpoint of the one of $v_j$. This ordering has the property that if $v_iv_j \in E(G)$ for $i < j$, then $\{v_i, \ldots , v_j\}$ is a clique [8, 16]. It is easy to see that if $v_i \in [v_j,v_k]^*_3$ for $j < k$, then $j \le i \le k$. In the next, we consider a canonical ordering $\varGamma = (v_1, v_2, \ldots , v_n)$ of a given unit interval graph G.

Lemma 1

If $v_j$ is simplicial, then $h^*_3(G) = h^*_3(G[\{v_1, \ldots , v_j\}]) + h^*_3(G[\{v_j, \ldots , v_n\}]) - 1$.

Proof

Let $S, S_1$, and $S_2$ be minimum hull sets of $G, G_1 = G[\{v_1 \ldots v_j\}]$, and $G_2 = G[\{v_j \ldots v_n\}]$, respectively. Since $\varGamma = (v_1, v_2, \ldots , v_n)$ is a canonical ordering and $v_j$ is a simplicial vertex of $G,G_1$, and $G_2$, it holds $S \supseteq \{v_j\} = S_1 \cap S_2$. It is clear that $S_1 \cup S_2$ is a hull set of G, and hence $h^*_3(G) \le h^*_3(G[\{v_1, \ldots , v_j\}]) + h^*_3(G[\{v_j, \ldots , v_n\}]) - 1$. Now, consider an induced path $v_iv_kv_{\ell }$ with $v_i \in V(G_1) \setminus \{v_j\}$ and $v_\ell \in V(G_2) \setminus \{v_j\}$. If $v_k \in V(G_2)$, then $i< j< k < \ell$ and $\{v_i, \ldots , v_k\}$ is a clique containing $v_j$. Since $v_j$ is simplicial, if $v_jv_\ell \in E(G)$, then $v_iv_{\ell } \in E(G)$, which would contradict the assumption that $v_iv_kv_{\ell }$ is an induced path. Therefore $v_jv_\ell \not \in E(G)$ and $v_k \in [v_j,v_\ell ]^*_3$. The case for $v_k \in V(G_1)$ is analogue. Hence, $S \cap V(G_i)$ is a minimum hull set of $G_i$ for $i \in [2]$, which means that $h^*_3(G) \ge h^*_3(G[v_1, \ldots , v_j]) + h^*_3(G[v_j, \ldots , v_n]) - 1$.    $\Box$

Due to Lemma 1, we can assume that G has only two simplicial vertices, namely, $v_1$ and $v_n$. In the sequel, we use the geodetic interval to obtain a useful partition of the vertices of G. We say that $v_i$ is a black vertex if $v_i$ lies in a shortest $(v_1,v_n)$-path and that it is a red vertex otherwise. The black vertices v such that $d(v_1,v) = i$ form the black region $B_i$. Note that all vertices of $B_i$ are consecutive in $\varGamma$. The set of vertices between the black regions $B_{i-1}$ and $B_i$ in $\varGamma$ form the red region $R_i$. These definitions induce a partition of $\varGamma$ into black and red regions $B_0, R_1, B_1, \ldots , R_q, B_q$. Note that a red region can be empty, $B_0 = \{v_1\}$, $B_q = \{v_n\}$, and $d(v_1,v_n) = q = d(G)$, where d(G) stands for the diameter of G. Besides, the black (and red) regions are precisely defined by the following two (not necessarily distinct) shortest $(v_1,v_n)$-paths, namely, the one whose internal vertices have all the highest possible indexes in $\varGamma$ and the one whose internal vertices have all the lowest possible indexes in $\varGamma$. Each black region $B_i$ contains precisely the vertices of those two paths having distance i to $v_1$ as well as all vertices between them in the canonical ordering $\varGamma$. (See Fig. 1.)

For $i \in [q]$, denote by $r^{\ell }_i$ and $r^r_i$ the leftmost and rightmost vertices of $R_i$ in $\varGamma$, respectively. For $i \in [q] \cup \{0\}$, denote by $b^{\ell }_i$ and $b^r_i$ the leftmost and rightmost vertices of $B_i$ in $\varGamma$, respectively. If, for $i \in [q]$, $b^{\ell }_{i-1}b^r_{i} \in E(G)$, then we say that $b^{\ell }_{i-1}b^r_{i}$ is a long edge. For $i \in [q]$, denote by $R^r_i$ the vertices of $R_i$ having edges to $R_{i+1}$ and by $R^{\ell }_i$ the vertices of $R_i$ having edges to $R_{i-1}$. We say that a red vertex $v \in R_i$ is a right vertex if $v \not \in R^{\ell }_i$ and that it is a left vertex if $v \not \in R^r_i$.

Let $\varTheta = (u_{k_1}, u_{k_2}, \ldots , u_{k_{|R|}})$ be the subordering of $\varGamma$ induced by the set of all red vertices $R = R_1 \cup \ldots \cup R_q$. A subordering $\varTheta _{i,j} = (u_{k_i}, \ldots , u_{k_j})$ for $i \le j$ is a component of G if $u_{k_i}$ is a right vertex, $u_{k_j}$ is a left vertex, there is no $i' \in [j-1] \setminus [i-1]$ such that $u_{k_{i'}}$ is a left vertex and $u_{k_{i'+1}}$ is a right vertex, and it is maximal (that is, it must hold that either $u_{k_{i-1}}$ is a left vertex or $i = 1$, and additionally, that either $u_{k_{j+1}}$ is a right vertex or $j = |R|$). If, in addition, for every $v_{k'} \in \varTheta _{i,j}$ there exists a long edge $v_{k''}v_{k'''} \in E(G)$ such that $k''< k' < k'''$, then $\varTheta _{i,j}$ is said to be a covered component. Note that a component can be a singleton. However, since we are assuming that G has only two simplicial vertices $v_1$ and $v_n$, a covered component can neither be a singleton nor intersect only one red region as its elements would be simplicial vertices different from $v_1$ and $v_n$. Thus, every covered component must contain vertices of at least two red regions. (See Fig. 1.) Finally, the components of a unit interval graph can be determined in linear time [9].

Fig. 1.

Here there are two components: $\{v_2,v_3,v_6,v_7\}$ (covered) and $\{v_8, v_{11}, v_{12}, v_{15} \}$ (not covered), as both red vertices $v_{11}$ and $v_{12}$ are not covered by a long edge such as $v_1v_5$, $v_4v_{10}$ and $v_{13}v_{16}$. Note that only edges between black vertices and between red vertices of distinct red regions are being depicted, and that the two shortest paths $v_1$ $v_4$ $v_9$ $v_{13}$ $v_{16}$ and $v_1$ $v_5$ $v_{10}$ $v_{14}$ $v_{16}$ define precisely the black (and red) regions. (Color figure online)

Now we present some structural results. In the next, we characterize some $P^*_3$-concave sets.

Lemma 2

It holds that:

• (a) for $i \in [q-1]$, $R^r_i \cup B_i \cup R_{i+1} \cup B_{i+1}$ is a $P^*_3$-concave set;

• (b) for $i \in [q-1]$, $R_i \cup B_i \cup R_{i+1} \cup B_{i+1}$ is a $P^*_3$-concave set;

• (c) for $i \in \{ 0\} \cup [q-2]$, $B_i \cup R_{i+1} \cup B_{i+1} \cup R_{i+2}$ is a $P^*_3$-concave set; and

• (d) for $i \in \{ 0\} \cup [q-1]$, if $R^{\ell }_{i+1} \cap R^r_{i+1} = \varnothing$, then $B_i \cup R_{i+1} \cup B_{i+1}$ is a $P^*_3$-concave set.

Proof

First note that if $\varGamma _{j,k} = (v_j, \ldots , v_k)$ for $j < k$ is the ordering of a set $S = \{v_j, \ldots , v_k\}$ in $\varGamma$, then all vertices in $\varGamma _{1,j-1}$ having a common neighbor in S are adjacent, and the same is true for all vertices in $\varGamma _{k+1,n}$ having a common neighbor in S. Thus, S is always a $P^{*}_{3}$-concave set for $j=1$. Besides, S is a $P^{*}_{3}$-concave set for $j > 1$ if the distance of any vertex of $\varGamma _{1,j-1}$ to any vertex of $\varGamma _{k+1,n}$ is at least 3.

(a) Take $S = R^r_i \cup B_i \cup R_{i+1} \cup B_{i+1}$. For $j > 1$, the fact that $v_{j-1}$ has no edges to $R_{i+1}$ implies that the distance of any vertex of $\varGamma _{1,j-1}$ to any vertex of $\varGamma _{k+1,n}$ is at least 3.

(b) By (a) and the fact that if $\varGamma _{j,k}$ is $P^{*}_{3}$-concave, then $\varGamma _{j',k'}$ is $P^{*}_{3}$-concave for $j' \le j$ and $k' \ge k$.

(c) By symmetry, this case is equivalent to (b).

(d) Now take $S = B_i \cup R_{i+1} \cup B_{i+1}$. For $j > 1$, $d(v_{j-1},v_{k+1}) \ge 3$ if $R^{\ell }_{i+1} \cap R^r_{i+1} = \varnothing$.    $\Box$

Next, we present a partition of $\varGamma$ into parts called C-sets and classify them into 4 types.

• If $\varTheta _{i,j} (u_{k_i}, \ldots , u_{k_j})$ is a covered component, then $\varGamma _{i',j'}$ is a C-set where $v_{i'} = u_{k_i}$ and $v_{j'} = u_{k_j}$. If $\varGamma _{i',j'}$ contains an odd number of black regions, then $\varGamma _{i',j'}$ has type 1. Otherwise $\varGamma _{i',j'}$ has type 2.

• If $\varGamma _{i,j}$ is maximal having no vertex belonging to a C-set of type 1 or 2, then $\varGamma _{i,j}$ is a C-set as well. If $\varGamma _{i,j}$ contains an odd number of black regions, then $\varGamma _{i,j}$ has type 3. Otherwise, $\varGamma _{i,j}$ has type 4.

For example, the unit interval graph of Fig. 1 gets partitioned into exactly three C-sets: $\varGamma _{1,1}$ (of type 3), $\varGamma _{2,7}$ (of type 1), and $\varGamma _{8,16}$ (of type 3). It is clear that the C-sets always form a partition of $\varGamma$. In fact, they also induce a partition of the black regions of G, i.e., all vertices of any black region are contained in a unique C-set and every C-set contains at least the vertices of one black region. These facts allow us to denote by $C_{i,j}$ the C-set whose set of black regions is $\{B_i, \ldots , B_j\}$. If $C_{i,j} \cap R_i \ne \emptyset$, then $C_{i,j} \cap R_i = R^r_i$. Similarly, if $C_{i,j} \cap R_{j+1} \ne \emptyset$, then $C_{i,j} \cap R_{j+1} = R^{\ell }_{j+1}$. Therefore, from now on, if not empty, both $R^r_i$ and $R^{\ell }_{j+1}$ as well as $R_k$ for $i< k < j+1$ will be called the red regions of $C_{i,j}$. Finally, note that those red regions might be empty if $C_{i,j}$ has type 3 or 4. However, if $C_{i,j}$ has type 1 or 2, then its red regions form a covered component, and consequently, not only both $R^r_i \ne \emptyset$ and $R^{\ell }_{j+1} \ne \emptyset$, but also both $R_k \ne \emptyset$ and $R^{\ell }_k \cap R^r_k \ne \emptyset$ for $i< k < j+1$, as a covered component does not contain a left vertex followed by a right vertex.

The proposed algorithm finds a $\{0,-1\}$ labeling of the C-sets, which depends on the types and the relative positions of the C-sets. A minimum $P^*_3$-hull set is then obtained by making a standard choice S for each C-set between two possibilities, which we call left and right choices, and depends on the pair type and label, as shown in Table 1. As in Figs. 2, 3, 4 and 5, for any C-set C, there is (at most) one black region B of C such that its standard choice alternates in containing and not containing a black vertex of each consecutive black region of C from B on. Besides those black vertices, the standard choice has one red vertex if C contains a covered component and no red vertex otherwise.

Table 1. Standard choices.

The left choice S for a C-set $C_{i,j}$ with type $t \in [4]$ and $k = j - i + 1$ black regions is defined as

$S = {\left\{ \begin{array}{ll} \{r^r_i\} \cup \{b^r_{i+1+2k'} : 0 \le k'< \lfloor \frac{k}{2} \rfloor \} &{} \text {, if } t \in [2]; \\ \{b^r_{i+2k'} : 0 \le k' < \lceil \frac{k}{2} \rceil \} &{} \text {, if } t \in \{3,4\}. \end{array}\right. }$

The right choice S for a C-set $C_{i,j}$ with type $t \in [4]$ and $k = j - i + 1$ black regions is defined as

$S = {\left\{ \begin{array}{ll} \{r\} \text { for some } r \in R^{\ell }_{i+1} &{} \text {, if } t = 1 \text { and } j = i; \\ \{r_{i+1}\} \cup \{b^r_{i+2k'} : 0< k'< \lceil \frac{k}{2} \rceil \} \text { for some } r_{i+1} \in R^{\ell }_{i+1} \cap R^r_{i+1} &{} \text {, if } t \in [2] \text { and } j > i;\\ \{b^r_{i+1+2k'} : 0 \le k' < \lfloor \frac{k}{2} \rfloor \} &{} \text {, if } t \in \{3,4\}. \end{array}\right. }$

Fig. 2.

Scheme representing the left (on top) and right (on bottom) choices of C-set $C_{i,i+4}$ with type 1. (Color figure online)

Fig. 3.

Scheme representing the left (on top) and right (on bottom) choices of C-set $C_{i,i+3}$ with type 2. (Color figure online)

The idea of the linear algorithm is to give the left choice for the first C-set, and then alternate the standard choice from left to right and vice-versa if and only if the preceding C-set had type 2 or 3. Note that label $-1$ means “missing” and indicates that no vertex of the last black region $B_j$ of $C_{i,j}$ belongs to its standard choice S. Note also that the first and the last C-sets in $\varGamma$ are not a covered component, and therefore, always have types in $\{3,4\}$. Figures 2, 3, 4 and 5 depict the left and right choices for a C-set depending on its type.

In the next lemma we show that, for any $j \in [q]$, if $B_{j-1}$ and $B_j$ belong to distinct C-sets, then there is no vertex of $R_j$ having neighbors in both $R_{j-1}$ and $R_{j+1}$.

Lemma 3

If $C_{i,j-1}$ and $C_{j,k}$ are C-sets, then $R^{\ell }_j \cap R^r_j = \varnothing$.

Proof

By definition, if one of these C-sets has type 3 or 4, then the other one has type 1 or 2. This means that exactly one of these two C-sets has type 1 or 2, and therefore the red vertices of this C-set form a covered component. However, if $R^{\ell }_j \cap R^r_j \ne \varnothing$, then there would be a contradiction, as no vertex in $R_j$ could be neither a left vertex nor a right vertex, i.e., neither the first nor the last red vertex of this C-set of type 1 or 2.    $\Box$

Lemma 4

Every covered component of a unit interval graph G is $P^*_3$-concave.

Proof

Let $C_{i,j}$ be the C-set of type either 1 or 2 containing the covered component, therefore, the red regions of $C_{i,j}$ form the covered component. Lemma 3 implies that, for $i< k < j+1$, each red vertex of $R_k$ neighbors only red vertices of $R_{k-1}$, $R_k$ and $R_{k+1}$, each red vertex of $R^r_i$ neighbors only red vertices of $R_i$ and $R_{i+1}$ and each red vertex of $R^{\ell }_{j+1}$ neighbors only red vertices of $R_j$ and $R_{j+1}$. Finally, for $i \le k \le j+1$, since $B_{k-1} \cup R_k \cup B_k$ form a clique and $R_k$ neighbors only black vertices of $B_{k-1} \cup B_k$, each vertex of the covered component is such that all its neighbors not belonging to the covered component form a clique, meaning that the covered component is $P^*_3$-concave, and therefore, every covered component of G must intersect with every $P^*_3$-hull set of G. (As an alternative proof, the fact that $\langle S \rangle ^*_3 \subseteq \langle S \rangle _g$ for every set $S \subseteq V(G)$ also implies the claim, as from [9] it is known that every covered component of G is geodesically concave.)    $\Box$

Remember that $b^r_{i-1}$ is the rightmost vertex of $B_{i-1}$, and that $b^{\ell }_{i+1}$ is the leftmost vertex of $B_{i+1}$, being both $b^r_{i-1}$ and $b^{\ell }_{i+1}$ adjacent to every vertex in $B_i$, but not to one another. Note also that $b^{\ell }_{i+1}$ has no neighbor in $R^r_i$, as no vertex in that set belongs to a shortest path between $v_1$ and $v_n$, and that $b^r_{i-1}$ has no neighbor in $R^{\ell }_{i+1}$, as no vertex in that set has distance i to $v_1$. The following property will be very useful.

Fig. 4.

Scheme representing the left (on top) and right (on bottom) choices of C-set $C_{i,i+4}$ with type 3. (Color figure online)

Fig. 5.

Scheme representing the left (on top) and right (on bottom) choices of C-set $C_{i,i+3}$ with type 4. (Color figure online)

Lemma 5

If $r \in R^r_i \cup R^{\ell }_{i+1}$, then $R^r_i \cup B_i \cup R^{\ell }_{i+1} \subseteq \langle \{b^r_{i-1}, r, b^{\ell }_{i+1}\} \rangle ^*_3$.

Proof

Note that $B_i \subseteq [b^r_{i-1},b^{\ell }_{i+1}]^*_3$ and that $R^r_i \ne \varnothing$ if and only if $R^{\ell }_{i+1} \ne \varnothing$. If $r \in R^r_i$ and $v_{k}$ is the vertex with maximum index k in $\varGamma$ belonging to $N(r) \cap R^{\ell }_{i+1}$, then $R^{\ell }_{i+1} \cap \varGamma _{1,k} \subseteq [\{r,b^{\ell }_{i+1}\}]^*_3$, $R^r_i \subseteq [\{b^r_{i-1}\} \cup (R^{\ell }_{i+1} \cap \varGamma _{1,k})]^*_3$, and $R^{\ell }_{i+1} \subseteq [R^r_i \cup \{b^{\ell }_{i+1}\}]^*_3$ as well. Similarly, in a symmetric way, if $r \in R^{\ell }_{i+1}$ and $v_{k'}$ is the vertex with minimum index $k'$ in $\varGamma$ belonging to $N(r) \cap R^r_i$, then $R^r_i \cap \varGamma _{k',n} \subseteq [\{r,b^r_{i-1}\}]^*_3$, $R^{\ell }_{i+1} \subseteq [\{b^{\ell }_{i+1}\} \cup (R^r_i \cap \varGamma _{k',n}) ]^*_3$ and $R^r_i \subseteq [R^{\ell }_{i+1}\cup \{b^r_{i-1}\}]^*_3$ as well.    $\Box$

Now we are ready to understand why the linear algorithm presented, which starts with a left choice for the first C-set and then flips the standard choice from left to right and vice-versa if and only if the preceding C-set has type 2 or 3, indeed provides a minimum $P^*_3$-hull set of G when the choices of the C-sets get united together with $v_n$. The following lemma throws light on that.

Lemma 6

If $S_{i,j}$ is a standard choice for a C-set $C_{i,j}$, then the following holds:

• (a) $C_{i,j} \subseteq \langle S_{i,j} \cup \{b^r_{i-1}, b^{\ell }_{j+1}\} \rangle ^*_3$;

• (b) $C_{i,j} \setminus (R^r_i \cup R^{\ell }_{i+1})\subseteq \langle S_{i,j} \cup B_i \cup \{b^{\ell }_{j+1}\} \rangle ^*_3$;

• (c) $C_{i,j} \setminus (R^r_{j} \cup R^{\ell }_{j+1}) \subseteq \langle S_{i,j} \cup B_j \cup \{b^r_{i-1}\} \rangle ^*_3$;

• (d) $C_{i,j} \setminus (R^r_{i} \cup R^{\ell }_{i+1} \cup R^r_{j} \cup R^{\ell }_{j+1}) \subseteq \langle S_{i,j} \cup B_i \cup B_j \rangle ^*_3$.

Proof

Write $S_a = S_{i,j} \cup \{b^r_{i-1}, b^{\ell }_{j+1}\}$, $S_b = S_{i,j} \cup B_i \cup \{b^{\ell }_{j+1}\}$, $S_c = S_{i,j} \cup B_j \cup \{b^r_{i-1}\}$, and ${S_d} = S_{i,j} \cup B_i \cup B_j$. We give only one proof for all four cases, thus let $x \in \{a, b, c, d\}$.

First consider $C_{i,j}$ with type in $\{1,2\}$, that is, its red regions form a covered component. It is clear that $B_i \subseteq [S_x]^*_3$ for $x \in \{a, b, c, d\}$. Since $b^{\ell }_kb^r_{k+1} \in E(G)$ for $i-1 \le k \le j$, we have $B_k \subseteq [[S_x]^*_3]^*_3 \subseteq \langle S_x \rangle ^*_3$ for $x \in \{a, b, c, d\}$ and $i \le k \le j$. Besides, for each choice $S_{i,j}$, note that there is $r \in S_{i,j}$ such that either $r = r^r_i$ (left choice) or $r \in R^{\ell }_{i+1} \cap R^r_{i+1}$ (right choice), and thus, not only $[S_x]^*_3 \cap R^{\ell }_{i+1} \cap R^r_{i+1} \ne \varnothing$ for $x \in \{a, b, c, d\}$ and $i < j$, but also by Lemma 5 we have that $R^r_i \cup R^{\ell }_{i+1} \subseteq \langle S_x \rangle ^*_3$ for either $x \in \{a, c\}$ and $i < j$, or $x = a$ and $i=j$. Now, since $R^{\ell }_{k+1} \cap R^r_{k+1} \ne \varnothing$ for $i \le k \le j-1$ as the red regions of $C_{i,j}$ form a covered component, due to Lemma 5 we have for $i < j$ by forwards induction starting on $[S_x]^*_3 \cap R^{\ell }_{i+1} \cap R^r_{i+1} \ne \varnothing$ that $R^r_{k+1} \cup R^{\ell }_{k+2} \subseteq \langle S_x \rangle ^*_3$ for either $x\in \{a, b\}$ and $i \le k \le j-1$, or $x \in \{c, d\}$ and $i \le k \le j-2$.

Now, consider that $C_{i,j}$ has type 3 or 4. Note that $\{b^r_k | i \le k \le j\} \subseteq [S_x]^*_3$ and $B_j \subseteq [[S_x]^*_3]^*_3$ for $x \in \{a, b, c, d\}$, which implies, by backwards induction starting on $B_j$, that $B_k \subseteq \langle S_x \rangle ^*_3$ for $x \in \{a, b, c, d\}$ and $i \le k \le j$. Therefore, if some red region $R_k$ for $i < k \le j$ is not covered by a long edge, then $R_k \subseteq [b^{\ell }_{k-1}, b^r_{k}]^*_3 \subseteq \langle S_x \rangle ^*_3$ for $x \in \{a, b, c, d\}$ as well. Thus, suppose that $(R_{i'}, \ldots , R_{j'})$ is a maximal sequence of covered non-empty red regions for $i+1 \le i' \le k \le j' \le j$. Since $C_{i,j}$ does not contain a covered component, $R_{i'-1} \supseteq R^r_{i'-1} \ne \emptyset$ with $i' > i+1$ or $R_{j'+1} \supseteq R^{\ell }_{j'+1}\ne \emptyset$ with $j' < j$ is not a covered red region. Without loss of generality, assume that $R_{i'-1} \supseteq R^r_{i'-1} \ne \emptyset$ with $i' > i+1$ is not a covered red region, meaning that $R_{i'-1} \subseteq \langle S_x \rangle ^*_3$ for $x \in \{a, b, c, d\}$. (Otherwise, an analogous argument using Lemma 5 works with a backwards induction instead of a forwards one.) Note that Lemma 5 applied on $b^r_{i'-2}, r^r_{i'-1}, b^{\ell }_{i'}$ yields $R^{\ell }_{i'} \subseteq \langle S_x \rangle ^*_3$. Now, as $C_{i,j}$ does not contain a covered component, $R^{\ell }_{k} \cap R^r_{k} \ne \varnothing$ for $i' \le k < j'$, implying by forwards induction that Lemma 5 applied on $b^r_{k-1}, r, b^{\ell }_{k+1}$ with $r \in R^{\ell }_{k} \cap R^r_{k}$ yields $R^r_{k} \cup R^{\ell }_{k+1} \subseteq \langle S_x \rangle ^*_3$ for either $i' \le k \le j'$ (if $R_{j'+1} \ne \varnothing$) or $i' \le k < j'$ (if $R_{j'+1} = \varnothing$), that is, $R_{k} \subseteq \langle S_x \rangle ^*_3$ for $i' \le k \le j'$, as either $R^{\ell }_{j'} \cap R^r_{j'} \ne \varnothing$ with $j' < j$ when $R_{j'+1} \ne \varnothing$ or $R_{j'} = R^{\ell }_{j'}$ when $R_{j'+1} = \varnothing$. Finally, it remains to show that $R^r_i \subseteq \langle S_x \rangle ^*_3$ for $x \in \{a, c\}$ and that $R^{\ell }_{j+1} \subseteq \langle S_x \rangle ^*_3$ for $x \in \{a, b\}$, but these facts are directly derived from Lemma 5, as in this case both $R_i$ and $R_{j+1}$ are covered red regions.    $\Box$

Let $(C_1, \ldots , C_t)$ be the C-sets ordered according to $\varGamma$. The set S returned by Algorithm 1 is a minimum $P^*_3$-hull set of G containing $v_n$ as well as the standard choices selected by the algorithm for the C-sets, based on both the types and the received labels. Remark that the label is applied in such a way that the algorithm gives the left choice for $C_1$, and then consecutively alternates the standard choice from left to right and vice-versa if and only if the preceding C-set had type 2 or 3, maintaining it otherwise. In Lemma 8 we prove that S is in fact a $P^*_3$-hull set of G, whereas in Lemmas 9 to 11 we prove that there is no $P^*_3$-hull set of G with less than |S| vertices. Define $f(C_i)$ as the cardinality of the standard choice that the algorithm associated with $C_i$ and $f'(G)$ as the number of times that the labeling changes from $-1$ to 0, plus 1 if $C_1$ has type 3, and again plus 1 if $C_t$ received label $-1$. In Theorem 1 we show that .

The next lemma combined with the previous one is key to comprehend the correctness.

Lemma 7

If $C_{i,j}$ is a C-set of G and S is the set returned by Algorithm 1, then $B_i \cup \ldots \cup B_j \subseteq \langle S \rangle ^*_3$. Hence, $b^r_{i-1} \in \langle S \rangle ^*_3$ for $1 \le i \le q$ and $b^{\ell }_{j+1} \in \langle S \rangle ^*_3$ for $0 \le j \le q - 1$.

Proof

First, consider the case where $C_{i,j}$ has type 3 or 4. Let $S_{i,j} = S \cap C_{i,j}$. We begin assuming that $i \ge 1$ and $j \le q - 1$. Observe that if $b^r_i \in S_{i,j}$, then there is $v \in S \cap (\{b^r_{i-2}\} \cup R_{i-1})$; otherwise there is $v \in S \cap (\{b^r_{i-1}\} \cup R_i)$. Observe also that if $b^r_j \in B$, then there is $w \in S \cap (\{b^r_{j+1},b^r_{j+2}\} \cup R_{j+2})$; otherwise there is $w \in S \cap (\{b^r_{j+1}\} \cup R_{j+1})$. In all cases, it holds that $b^r_k \in [S_{i,j} \cup \{v,w\}]^*_3$ for $i-1 \le k \le j+1$. Since $C_{i,j}$ has type 3 or 4, the C-set containing $B_{j+1}$ has type 1 or 2, which means that the edge $b^{\ell }_jb^r_{j+1}$ exists. Hence $b^{\ell }_j \in \langle S \rangle ^*_3$, which implies that $B_i \cup \ldots \cup B_j \subset \langle S \rangle ^*_3$. Now, if $i = 0$, then $B_i = \{v_1\}$ and $b^r_i = v_1 \in S$; and if $j = q$, then $B_j = \{v_n\}$ and $b^{\ell }_j = v_n \in S$, which means that $B_i \cup \ldots \cup B_j \subset \langle S \rangle ^*_3$ even if for $i = 0$ or $j = q$.

Now, consider the case where $C_{i,j}$ has type 1 or 2. Note that the first C-set $C_1$ as well as the last C-set $C_t$ have both types in $\{3,4\}$. Thus, a C-set $C_{i,j}$ of type in $\{1,2\}$ is such that not only $0< i \le j < q$, but also both its preceding and subsequent C-sets have types in $\{3,4\}$. This fact jointly with both the previous case and (a) of Lemma 6 imply that $B_i \cup \ldots \cup B_j \subseteq \langle S \rangle ^*_3$.    $\Box$

Lemma 8

Algorithm 1 returns a $P^*_3$-hull set of G.

Proof

Recall that G has exactly 2 simplicial vertices. Let S be the set returned by Algorithm 1 and $C_{i,j}$ be a C-set of G having type t. Consider first $i = 0$. If $i=0$, $B_i = \{v_1\} \subseteq S$ and clearly by definition $R_0^r \cup R^{\ell }_{1} = \emptyset$. If $j = q$, $B_j = \{v_n\} \subseteq S$ and clearly by definition $R_q^r \cup R^{\ell }_{q+1} = \emptyset$. By (d) of Lemma 6, $V(G) = C_{i,j} = \langle S \rangle ^*_3$. Now, consider that $j < q$. By Lemma 7, it holds $b^{\ell }_{j+1} \in \langle S \rangle ^*_3$. Thus, by (b) of Lemma 6, $C_{i,j} \subseteq \langle S \rangle ^*_3$. Next, consider $j = q$ and $i > 0$. By Lemma 7, $b^r_{i-1} \in \langle S \rangle ^*_3$. By (c) of Lemma 6, $C_{i,j} \subseteq \langle S \rangle ^*_3$. Finally, suppose $i > 0$ and $j < q$. By Lemma 7, $b^r_{i-1}, b^{\ell }_{j+1} \in \langle S \rangle ^*_3$. By (a) of Lemma 6, $C_{i,j} \subseteq \langle S \rangle ^*_3$.    $\Box$

We now define a lower bound, proved in Lemma 9, for the number of vertices that any $P^*_3$-hull set contains from a C-set $C_{i,j}$ as a function of its type t.

$f(C_{i,j}) = {\left\{ \begin{array}{ll} \frac{j-i+1}{2} &{} \text {, if } t \in \{2,4\}; \\ \frac{j-i+2}{2} &{} \text {, if } t = 1; \\ \frac{j-i}{2} &{} \text {, if } t = 3. \end{array}\right. }$

Let $S_{i,j}$ be a standard choice of $C_{i,j}$. Note that $f(C_{i,j}) = |S_{i,j}|$ if $t \in \{1,4\}$ or $S_{i,j}$ is a right choice; otherwise, $f(C_{i,j}) = |S_{i,j}| - 1$.

Lemma 9

If S is a $P^*_3$-hull set and $C_{i,j}$ is a C-set of a unit interval graph G, then $|S \cap C_{i,j}| \ge f(C_{i,j})$.

Proof

The number of black regions contained in $C_{i,j}$ is $j-i+1$. By Lemma 2 (a), $R^r_i \cup B_i \cup R_{i+1} \cup B_{i+1}$ is a $P^*_3$-concave set and $R_k \cup B_k \cup R_{k+1} \cup B_{k+1}$ is a $P^*_3$-concave set for $i +1 \le k \le j-1$. Therefore, $C_{i,j}$ contains at least $\lfloor \frac{j-i+1}{2} \rfloor$ disjoint $P^*_3$-concave sets, which implies the result if the type of $C_{i,j}$ is 2 or 4 as $j - i + 1$ is even or if its type is 3 as $j-i$ is not only even but also smaller than $j-i+1$.

Now, consider that $C_{i,j}$ has type 1 and let S be a $P^*_3$-hull set of G. By definition, $j-i + 1$ is odd. Since $C_{i,j}$ contains a covered component, Lemma 4 implies that at least one vertex of a red region of $C_{i,j}$ belongs to S. Now, due to this fact, if $|S \cap C_{i,j}| < \lceil \frac{j-i+1}{2}\rceil$, then there are four consecutive regions of $\varGamma$, w.l.o.g. say $V' = R_{i'} \cup B_{i'} \cup R_{i'+1} \cup B_{i'+1}$ for $i \le i' < j$ such that $V' \cap S = \varnothing$. By Lemma 2, $V'$ is a $P^*_3$-concave set, which is a contradiction. Thus, the result also holds for type 1.    $\Box$

Lemma 10

Let S be a $P^*_3$-hull set and let $C_{i,j}$ be a C-set of G such that $|S \cap C_i| = f(C_i)$.

• (a) If $C_{i,j}$ has type 2, then $S \cap (R^r_i \cup B_i \cup B_j \cup R^{\ell }_{j+1}) = \varnothing$;

• (b) If $C_{i,j}$ has type 1 or 4, then $S \cap (R^r_i \cup B_i) = \varnothing$ or $S \cap (B_j \cup R^{\ell }_{j+1}) = \varnothing$;

• (c) If $C_{i,j}$ has type 3, then $S \cap (R^r_i \cup B_i \cup R_{i+1} \cup R_j \cup B_j \cup R^{\ell }_{j+1}) = \varnothing$.

Proof

We first count the number of regions of $C_{i,j}$ in terms of $f(C_{i,j})$. (a) Suppose for contradiction that $v \in S \cap (R^r_i \cup B_i \cup B_j \cup R^{\ell }_{j+1})$. By symmetry, assume that $S \cap (R^r_i \cup B_i) \ne \varnothing$. The number of black regions of $C_{i,j}$ is $j - i + 1$, which means that $C_{i,j}$ has $2(j-i+1)+1 = 4f(C_{i,j})+1$ regions, namely, $R^r_i, B_i, R_{i+1}, B_{i+1}, \ldots , R_j, B_j, R^{\ell }_{j+1}$. (b) First, consider that $C_{i,j}$ has type 1. Suppose for contradiction that $S \cap (R^r_i \cup B_i) \ne \varnothing$ and $S \cap (B_j \cup R^{\ell }_{j+1}) \ne \varnothing$. Then, $C_{i,j}$ has $2(j-i+1)+1 = 2(j-i+2)-1 = 4f(C_{i,j})-1$ regions. Now, consider that $C_{i,j}$ has type 4. Suppose for contradiction that $S \cap (R^r_i \cup B_i) \ne \varnothing$ and $S \cap (B_j \cup R^{\ell }_{j+1}) \ne \varnothing$. Then, $C_{i,j}$ has $2(j-i+1)+1 = 4f(C_{i,j})+1$ regions. (c) Suppose for contradiction that $v \in S \cap (R^r_i \cup B_i \cup R_{i+1} \cup R_j \cup B_j \cup B^{\ell }_{j+1})$. By symmetry, assume $v \in R^r_{i-1} \cup B_i \cup R_i$. Then, $C_{i,j}$ has $2(j-i+1)+1 = 2(j-i)+3 = 4f(C_{i,j})+3$ regions.

Besides, by Lemma 4, S contains a vertex of a red region of $C_{i,j}$ if its type is either 1 or 2 (that is, if it contains a covered component). Now, using the pigeonhole principle in all (a), (b) and (c) items, we conclude that in all cases there are four consecutive regions of $C_{i,j}$ having no vertices of S. By Lemma 2, these four regions form a $P^*_3$-concave set, which implies that S is not a $P^*_3$-hull set of G, a contradiction.    $\Box$

Lemma 11

Consider the labeling obtained by Algorithm 1 and let S be a minimum $P^*_3$-hull set of G. The following sentences hold:

• (a) If $(C_i, \ldots , C_j)$ is a maximal sequence of C-sets such that $label(C_j) = 0$ and $label(C_k) = -1$ for $i \le k < j$, then $|S \cap (C_i \cup \ldots \cup C_j)| \ge f(C_i) + \ldots + f(C_j) + 1$; and

• (b) If $C_{j-1}$ and $C_j = C_{\ell _j,d(G)}$ are C-sets and $label(C_j) = -1$, then $|S \cap (C_{j-1} \cup C_j)| \ge f(C_{j-1})+f(C_j)+1$.

Proof

(a) Suppose that $|S \cap (C_i \cup \ldots \cup C_j)| \le f(C_i) + \ldots + f(C_j)$. If $j = 1$, then $C_j$ has type 3. By Lemma 10, $S \cap B_0 = \varnothing$, which is a contradiction since $B_0 = \{v_1\}$ and $v_1$ is a simplicial vertex. Then consider $j > 1$. Remember that a C-set has label different of its predecessor if and only if its type is 2 or 3. Hence, $C_j = C_{j',j''}$ has type 2 or 3. By Lemma 10, it holds $S \cap (R^r_{j'} \cup B_{j'}) = \varnothing$. If $i = 1$, then $C_1 = C_{0,\ell _2-1}$ has type 4. Since $v_1$ is a simplicial vertex, $v_1 \in S$, then, by Lemma 10, $S \cap (B_{\ell _2-1} \cup R^{\ell }_{\ell _2}) = \varnothing$. If $i \ge 2$, then $C_i = C_{\ell _i,\ell _{i+1}-1}$ has type 2 or 3. By Lemma 10, $S \cap (B_{\ell _2-1} \cup R^{\ell }_{\ell _2}) = \varnothing$. In both cases, $C_k = C_{\ell _k,\ell _{k+1}-1}$ has type 1 or 4 for $i+1 \le k < j$. This means by Lemma 10 that $S \cap (R^r_{\ell _k} \cup B_{\ell _k}) = \varnothing$ or $S \cap (B_{\ell _{k+1}-1} \cup R^{\ell }_{\ell _{k+1}}) = \varnothing$ for $i+1 \le k < j$. Therefore, by the pigeonhole principle, there is some $p \in \{i+1, \ldots , j\}$ such that $B_{\ell _p} \cup R^r_{\ell _p+1} \subset C_{\ell _{p-1},\ell _p-1}$ and $R^{\ell }_{p+1} \cup B_{p+1} \subset C_{\ell _p,\ell _{p+1}-1}$ such that $S \cap (B_p \cup R_{p+1} \cup B_{p+1}) = \varnothing$. By Lemmas 2 (d) and 3, $B_p \cup R_{p+1} \cup B_{p+1}$ is a $P^*_3$-concave set, which contradicts the assumption that S is a $P^*_3$-hull set.

(b) Suppose that $|S \cap (C_{j-1} \cup C_j)| \le f(C_{j-1})+f(C_j)$. We know that $C_j$ has type $t \in \{3,4\}$, $C_{j-1}$ has type 1 or 2, $B_{d(G)} = \{v_n\}$, and $R_{d(G) + 1} = \varnothing$. If $t = 3$, then Lemma 10 (c) implies that $S \cap (R^r_i \cup B_i \cup R_{i+1} \cup R_{d(G)} \cup B_{d(G)}) = \varnothing$. But this is a contradiction because $v_n \in S$. Then consider $t = 4$. By Lemma 10 (b), $S \cap (R^r_{\ell _j} \cup B_{\ell _j}) = \varnothing$ or $S \cap B_{d(G)} = \varnothing$. Since $v_n \in S$, it holds $S \cap (R^r_{\ell _j} \cup B_{\ell _j}) = \varnothing$. Note that $label(C_{j-1}) = -1$. Let $(C_i, \ldots , C_j)$ be the maximal sequence of C-sets such that $label(C_k) = -1$ for $i \le k \le j$. Note that $C_k$ has type 1 or 4 for $i < k \le j$. Write $C_k = C_{\ell _k, \ell _{k+1}-1}$ for $i \le k < j$. Consider first $i = 1$. By the algorithm, $C_1 = C_{0,\ell _2-1}$ has type 4. By Lemma 10 (b), $B_0 \cap S = \varnothing$ or $(B_{\ell _2-1} \cup R^{\ell }_{\ell _2}) \cap S = \varnothing$. Since $v_1 \in B_0$ is a simplicial vertex, it holds $(B_{\ell _2-1} \cup R^{\ell }_{\ell _2}) \cap S = \varnothing$. Now consider $i > 1$. The algorithm implies that $C_i$ has type 2 or 3. Lemmas 10 (a) and (c) imply that $(B_{\ell _{i+1}-1} \cup R^{\ell }_{\ell _{i+1}}) \cap S = \varnothing$. Thus, in any case, Lemma 10 (b) implies that $S \cap (R^r_{\ell _k} \cup B_{\ell _k}) = \varnothing$ or $S \cap (B_{\ell _{k+1}-1} \cup R^{\ell }_{\ell _{k+1}}) = \varnothing$ for $i< k < j$. This means that there is some $p \in \{i+1, \ldots , j\}$ such that $S \cap (B_p \cup R_{p+1} \cup B_{p+1}) = \varnothing$, which is a contradiction by Lemmas 2 and 3.    $\Box$

Theorem 1

If G is a unit interval graph with exactly two simplicial vertices, then $h^*_3(G) = f'(G) + \underset{1 \le i \le t}{\sum } f(C_i)$. Besides, the $P^*_3$-hull number of a unit interval graph G can be found in linear time.

Proof

Consequence of Lemmas 8, 9, 10, and 11. Besides, a canonical ordering of a unit interval graph can be found in linear time [8, 16], and thus, its simplicial vertices as well. Since the components of a unit interval graph can be determined in linear time [9], the result follows due to Lemma 1.    $\Box$

3 Chordal Graphs

We conclude by pointing out the succeeding NP-completeness for the superclass of chordal graphs.

Theorem 2

Given a chordal graph G and an integer k, it is NP-complete to decide whether $h^*_3(G) \le k$.

The main idea behind the NP-completeness proof (omitted here due to lack of space) is a polynomial reduction from a restricted version of Satisfiability which is NP-complete [10, 12] . Let $\mathcal{C}$ be an instance of Satisfiability consisting of m clauses $C_1,\ldots ,C_m$ over n boolean variables $x_1,\ldots ,x_n$ such that every clause in $\mathcal{C}$ contains at most three literals and, for every variable $x_i$, there are exactly two clauses in $\mathcal{C}$, say $C_{j_i^{1}}$ and $C_{j_i^{2}}$, that contain the literal $x_i$, and exactly one clause in $\mathcal{C}$, say $C_{j_i^{3}}$, that contains the literal $\bar{x}_i$, and these three clauses are distinct.

Let the graph G be constructed as follows starting with the empty graph. For every $j\in [m]$, add a vertex $c_j$. For every $i\in [n]$, add 10 vertices $x_i,y_i,z_i,x_i^1,x_i^2,w_i^1,w_i^2,\bar{x_i},\bar{y}_i,\bar{w_i}$ and 17 edges to obtain the subgraph indicated in Fig. 6. Add a vertex z and the edges to make a clique of $C \cup Z \cup \{z\}$, where $C = \{c_j | j \in [m]\}$ and $Z =\{z_i | i \in [n]\}$. Setting $k = 4n+1$, we show in the full version of the paper that $\mathcal C$ is satisfiable if and only if G contains a $P^*_3$-hull set of order at most k.

Fig. 6.

When the construction of G ends, $z_i$ will belong to the clique $C \cup \{z_1, \ldots , z_n\} \cup \{z\}$.