Happy Set Problem on Subclasses of Co-comparability Graphs

Abstract

In this paper, we investigate the complexity of the Maximum Happy Set problem on subclasses of co-comparability graphs. For a graph G and its vertex subset S, a vertex $v \in S$ is happy if all v’s neighbors in G are contained in S. Given a graph G and a non-negative integer k, Maximum Happy Set is the problem of finding a vertex subset S of G such that $|S|= k$ and the number of happy vertices in S is maximized. In this paper, we first show that Maximum Happy Set is NP-hard even for co-bipartite graphs. We then give an algorithm for n-vertex interval graphs whose running time is $O(n^2 + k^3n)$; this improves the best known running time $O(kn^8)$ for interval graphs. We also design algorithms for n-vertex permutation graphs and d-trapezoid graphs which run in $O(n^2 + k^3n)$ and $O(n^2 + d^2(k+1)^{3d}n)$ time, respectively. These algorithmic results provide a nice contrast to the fact that Maximum Happy Set remains NP-hard for chordal graphs, comparability graphs, and co-comparability graphs.

1 Introduction

Easley and Kleinberg [2] said that homophily is one of the most basic notions governing the structure of social networks. Homophily is the principle that we are likely to associate with people who are similar in characteristics, such as their ages, their occupations, and their interests. Motivated from homophily of social networks, Zhang and Li [3] formulated two graph coloring problems, and recently Asahiro et al. [4] introduced another formulation on graphs. In this paper, we study the latter formulation, defined as follows.

For a graph $G=(V,E)$ and a subset $S \subseteq V$, a vertex $v \in S$ is happy if all its neighbors in G are contained in S. Given an undirected graph $G=(V,E)$ and a non-negative integer k, Maximum Happy Set is the problem of finding a subset $S \subseteq V$ such that $|S| = k$ and the number of happy vertices in S is maximized. For example, the set $S=\{v_1,v_2,v_6,v_7\}$ in Fig. 1b is an optimal solution to Maximum Happy Set for the graph G in Fig. 1a and $k=4$, where only two vertices $v_1$ and $v_7$ are happy.

Fig. 1

a A graph G, and b an optimal solution $S = \{v_1,v_2,v_6,v_7\}$ for G and $k=4$, where only $v_1$ and $v_7$ are happy vertices

1.1 Known Results

Although Maximum Happy Set was proposed recently,¹ it has been already studied from various viewpoints such as polynomial-time solvability, approximability, and fixed-parameter tractability.

Polynomial-Time Solvability: Maximum Happy Set is NP-hard even for bipartite graphs [5], cubic graphs [5], and split graphs [4]. On the other hand, the problem is solvable in $O(k^2n)$ time for block graphs [5], and solvable in $O(kn^8)$ time for interval graphs [5], where n is the number of vertices in a graph.

Approximability: Maximum Happy Set admits a polynomial-time approximation algorithm whose approximation ratio depends on the maximum degree of a graph [5].

Fixed-Parameter Tractability: Maximum Happy Set is W[1]-hard when parameterized by k even on split graphs [4], and hence it is very unlikely that the problem admits a fixed-parameter algorithm even when restricted to split graphs and parameterized by k. On the other hand, the problem admits fixed-parameter algorithms when parameterized by graph structural parameters such as tree-width, clique-width, neighborhood diversity, and twin-cover number of a graph [4].

1.2 Our Contributions

In this paper, we further investigate the polynomial-time solvability of Maximum Happy Set, by focusing on subclasses of co-comparability graphs. In particular, we consider co-bipartite graphs, interval graphs, permutation graphs and d-trapezoid graphs. See the relationship of graph classes illustrated in Fig. 2.

Fig. 2

Our results together with known ones for Maximum Happy Set on subclasses of perfect graphs. Each arrow represents the inclusion relationship between graph classes: $A \rightarrow B$ means that the graph class B is a subclass of the graph class A

We first show that Maximum Happy Set is NP-hard even for co-bipartite graphs. As far as we know, this is the first intractability result of Maximum Happy Set on subclasses of co-comparability graphs. We thus need to focus on other subclasses of co-comparability graphs, in order to seek polynomial-time solvable cases, as below.

We then give a polynomial-time algorithm for interval graphs. Recall that the polynomial-time solvability for interval graphs is already known [5]. However, our algorithm runs in $O(n^2 + k^3n)$ time for n-vertex interval graphs, which improves the best known running time $O(kn^8)$ [5].

We finally extend our algorithmic techniques for interval graphs to permutation graphs and d-trapezoid graphs, and give algorithms for n-vertex permutation graphs and d-trapezoid graphs which run in $O(n^2 + k^3n)$ and $O(n^2 + d^2(k+1)^{3d}n)$ time, respectively. These are new polynomial-time solvable cases, and give a nice contrast to the known fact that Maximum Happy Set is NP-hard for comparability graphs and co-comparability graphs (see also Fig. 2). We note that if k and d are fixed constants, then all of our algorithms in this paper run in $O(n^2)$ time.

1.2.1 Technical highlight

Our polynomial-time algorithms for interval graphs, permutation graphs and d-trapezoid graphs employ basically the same technique, that is, a dynamic programming approach based on graph representation models. Details and formal definitions will be given later, but we here explain the key point. Given an n-vertex graph $G=(V,E)$, we define a subgraph $G_i = (V_i, E_i)$ for each integer $i = 1, 2, \ldots , n$, depending on a representation model for G. Then, we wish to compute a partial solution $S_i = S^*\cap V_i$ for each $G_i$, where $S^*$ is an optimal solution of G. Note that $S_i$ is not always optimal for $G_i$, and hence it is not enough to compute an optimal solution of $G_i$. The key of our algorithms is that partial solutions $S_i$ of $G_i$ can be characterized by only two vertices that are not contained in $S^*$ if G is an interval graph or a permutation graph, and characterized by 2d vertices that are not contained in $S^*$ if G is a d-trapezoid graph. This efficient characterization of partial solutions leads to improving the running time for interval graphs.

1.3 Contrasts to Related Results

Our initial motivation was to develop a polynomial-time algorithm for Maximum Happy Set on co-comparability graphs, because it is known that several classical problems are tractable for co-comparability graphs even if they are NP-hard on perfect graphs (see again Fig. 2). Such examples include Minimum Dominating Set [6], Hamiltonian Cycle [7], and Minimum Feedback Vertex Set [8]. Our result of NP-hardness for co-comparability graphs gives an interesting contrast to these complexity examples.

The Densest $k$-Subgraph problem [9], which has been studied for more than two decades in the field of graph theory, can be seen as an edge variant of Maximum Happy Set: given an undirected graph $G=(V,E)$ and a non-negative integer k, the task of the problem is to find a vertex subset $S\subseteq V$ of size exactly k such that the number of edges whose both endpoints are contained in S is maximized. Interestingly, the complexity of Densest $k$-Subgraph remains open for interval graphs, permutation graphs, and planar graphs. Although results on Maximum Happy Set cannot be converted directly to Densest $k$-Subgraph, our complexity results in this paper may give new insights to Densest $k$-Subgraph.

2 Preliminaries

Let $G = (V,E)$ be a graph; we denote by V(G) and E(G) the vertex set and the edge set of G, respectively. We assume that all graphs in this paper are simple, undirected, and unweighted. For a vertex v of G, we denote by $N_{G}(v)$ and $N_{G}[v]$ the open and closed neighborhood of v in G, respectively, that is, $N_{G}(v)= \{ w \in V(G): vw \in E(G) \}$ and $N_{G}[v] = N_{G}(v)\cup \{v\}$. For a vertex subset $V^\prime \subseteq V$, we denote by $G-V^\prime$ the subgraph of G obtained by deleting all the vertices in $V^\prime$ and their incident edges. We shall often write $G-v$ instead of $G-\{v\}$ for a vertex $v \in V$.

For a graph $G = (V,E)$ and its vertex subset $S\subseteq V$, we say that a vertex $v \in V$ is happy with respect to S if $N_{G}[v] \subseteq S$; otherwise v is unhappy with respect to S. We denote by $H(G{;}S)$ the set of happy vertices with respect to S. We note that $H(G{;}\emptyset ) = \emptyset$. Given a graph $G = (V,E)$ and a non-negative integer k, Maximum Happy Set is the problem of finding a vertex subset $S\subseteq V$ such that $|S| = k$ and the size of $H(G{;}S)$ is maximized. For simplicity, our algorithms in this paper only compute the maximum value of $|H(G{;}S)|$. However, one can easily modify the algorithms so that they find an actual subset S in the same time complexity.

3 NP-Hardness for Co-bipartite Graphs

A graph is co-bipartite if it is the complement of a bipartite graph. In other words, a co-bipartite graph is a graph whose vertex set can be partitioned into two cliques. In this section, we give the following hardness result.

Theorem 1

Maximum Happy Set is NP-hard for co-bipartite graphs.

Proof

We give a polynomial-time reduction from Maximum Happy Set on general graphs to Maximum Happy Set on co-bipartite graphs. Let (G, k) be an instance of Maximum Happy Set on general graphs. We construct an instance $(G^\prime , k^\prime )$ of Maximum Happy Set on co-bipartite graphs from (G, k) as follows. Let $n = |V(G)|$ and $V(G) = \{v_1, v_2, \ldots , v_n\}$. The graph $G^\prime$ consists of disjoint two cliques whose vertex subsets are $A = \{a_1, a_2, \ldots , a_n\}$ and $B= \{b_1, b_2, \ldots , b_{n+k+1}\}$. In addition, $G^\prime$ has an edge $a_ib_j$ if and only if $i=j$ or $v_iv_j\in E(G)$ for each $i, j \in \{1, 2, \ldots , n\}$. This completes the construction of $G^\prime$, and we let $k^\prime = n+k$. Clearly, this reduction can be done in polynomial time.

We show that for any integer $\ell \ge 0$, there exists a subset $S \subseteq V(G)$ such that $|S| = k$ and $|H(G{;}S)| \ge \ell$ if and only if there exists a subset $S^\prime \subseteq V(G^\prime )$ such that $|S^\prime | = k^\prime$ and $|H(G^\prime {;}S^\prime )| \ge \ell$.

We first prove the necessity. Assume that there exists a subset $S\subseteq V(G)$ such that $|S| = k$ and $|H(G{;}S)| \ge \ell$. Let $S^\prime = A \cup \{b_j \mid v_j \in S\}$. Clearly, $|S^\prime | = n + k = k^\prime$. To show that $|H(G^\prime {;}S^\prime )| \ge \ell$, we indicate that for any happy vertex $v_i \in H(G{;}S)$, the corresponding vertex $a_i \in A$ of $G^\prime$ is also happy with respect to $S^\prime$. Obviously, $N_{G^\prime }[a_i]\cap A \subseteq S^\prime$. Moreover, since $v_i$ is happy with respect to S on G, any vertex $v_j \in N_{G}[v_i]$ is in S. By the construction of $S^\prime$, we have $b_j \in S^\prime$ that is adjacent to $a_i$ on $G^\prime$. Therefore, $N_{G^\prime }[a_i] \subseteq S^\prime$, that is, $a_i \in H(G^\prime {;}S^\prime )$. This implies that $|H(G^\prime {;}S^\prime )| \ge |H(G{;}S)| \ge \ell$.

Conversely, we prove the sufficiency. Assume that there exists a subset $S^\prime \subseteq V(G^\prime )$ such that $|S^\prime | = k^\prime = n+k$ and $|H(G^\prime {;}S^\prime )| \ge \ell$. Since $|S^\prime | = n+k$ and B forms a clique of $n+k+1$ vertices, at least one vertex $b_j \in B$ is not in $S^\prime$ and hence all vertices in B are unhappy with respect to $S^\prime$. This means that any happy vertex with respect to $S^\prime$ is in A. In the remainder of this proof, we assume that $A \subseteq S^\prime$; otherwise $|H(G^\prime {;}S^\prime )| = 0$. In addition, if there exists a vertex $b_j \in S^\prime$ for an integer j with $n+1\le j \le n+k+1$, then we remove $b_j$ from $S^\prime$ and arbitrarily add a vertex $b_{j^\prime } \notin S^\prime$ into $S^\prime$ for an integer $j^\prime \in \{1, \ldots , n\}$. We denote by $S^{\prime \prime }$ a set obtained by repeating this operation until $S^{\prime \prime } \cap \{b_{n+1}, \ldots , b_{n+k+1}\} = \emptyset$. Since no vertex in A is adjacent to $b_j$ for an integer $j \in \{n+1,\ldots , n+k+1\}$ from the construction of $G^\prime$, $H(G^\prime {;}S^\prime ) \subseteq H(G^\prime {;}S^{\prime \prime })$ holds. Let $S = \{v_j \mid j\in \{1,2,\ldots ,n\} \text {~and~} b_j \in S^{\prime \prime } \}$. Notice that, since $S^{\prime \prime }$ contains all vertices in A, we have $|S| = |S^{\prime \prime }| - |A| = k$. We now show that for any happy vertex $a_i \in H(G^\prime {;}S^{\prime \prime })$, the corresponding vertex $v_i \in V(G)$ is also happy with respect to S. Since $a_i$ is happy, any vertex $b_j \in N_{G^\prime }[a_i] \cap B$ is in $S^{\prime \prime }$ and hence $v_j \in S$. This implies that $N_{G}[v_i] \subseteq S$, that is, $v_i \in H(G{;}S)$. Therefore, $|H(G{;}S)| \ge |H(G^\prime {;}S^{\prime \prime })| \ge |H(G^\prime {;}S^\prime )| \ge \ell$. This completes the proof. $\square$

4 Polynomial-Time Algorithm for Interval Graphs

A graph $G = (V,E)$ with vertices $v_1, v_2, \ldots , v_n$ is called an interval graph if, for some set ${\mathcal {I}} = \{I_1, I_2, \dots , I_n\}$ of intervals on the real line, there is a one-to-one correspondence between V and ${\mathcal {I}}$ such that $v_iv_j \in E$ if and only if $I_i$ intersects $I_j$ for each $i,j\in \{1,2,\ldots , n\}$. Such a set ${\mathcal {I}}$ of intervals is called an interval representation of G. For instance, Fig. 3 shows the interval representation and its corresponding interval graph. In this section, we give a polynomial-time algorithm for Maximum Happy Set on interval graphs.

Theorem 2

Given an n-vertex interval graph G and a non-negative integer k, Maximum Happy Set is solvable in $O(n^2 + k^3n)$ time.

Fig. 3

a The interval representation and b its corresponding interval graph

Before the detailed description of our algorithm, we give the following simple but useful lemma.

Lemma 3

Let $G = (V,E)$ be a graph, and let $V^\prime$ and S be subsets of V. Then, it holds that $H(G{;}S) {\setminus } V^\prime \subseteq H(G - V^\prime {;}S{\setminus } V^\prime )$. Moreover, if $V^\prime \subseteq S$, then it holds that $H(G{;}S) {\setminus } V^\prime = H(G - V^\prime {;}S{\setminus } V^\prime )$.

Proof

We first prove the former statement. The case of $H(G{;}S) {\setminus } V^\prime = \emptyset$ is trivial. Suppose that $H(G{;}S) \setminus V^\prime \ne \emptyset$ and consider a vertex $v\in H(G{;}S) \setminus V^\prime$. Since $N_{G}[v] \subseteq S$ holds from the definition, $N_{G-V^\prime }[v] \subseteq S\setminus V^\prime$. This implies that $v \in H(G - V^\prime {;}S\setminus V^\prime )$, that is, $H(G{;}S) {\setminus } V^\prime \subseteq H(G - V^\prime {;}S{\setminus } V^\prime )$.

To prove the latter statement, we also show that $H(G - V^\prime {;}S{\setminus } V^\prime ) \subseteq H(G{;}S) {\setminus } V^\prime$ if $V^\prime \subseteq S$. The case of $H(G - V^\prime {;}S{\setminus } V^\prime ) = \emptyset$ is trivial and hence assume that there is a vertex $v\in H(G - V^\prime {;}S{\setminus } V^\prime )$. Since $N_{G-V^\prime }[v] \subseteq S{\setminus } V^\prime$ and $V^\prime \subseteq S$, we have $N_{G}[v] \subseteq S$, that is, $v \in H(G{;}S)$. It follows from $v\notin V^\prime$ that $v \in H(G{;}S){\setminus } V^\prime$ and thus $H(G - V^\prime {;}S{\setminus } V^\prime ) \subseteq H(G{;}S) {\setminus } V^\prime$. $\square$

Notice that Lemma 3 is applicable to general graphs as well as interval graphs.

To explain our algorithm, we need several assumptions and notations. Given an interval graph G, an interval representation ${\mathcal {I}}$ of G can be constructed in linear time [10,11,12]. For a subset ${\mathcal {S}} \subseteq {\mathcal {I}}$, we say that an interval $I \in {\mathcal {I}}$ is happy with respect to ${\mathcal {S}}$ if $I^\prime \in {\mathcal {S}}$ for every interval $I^\prime$ such that $I \cap I^\prime \ne \emptyset$. It is easy to see that for a subset ${\mathcal {S}}\subseteq {\mathcal {I}}$ and its corresponding vertex subset $S \subseteq V(G)$, an interval $I \in {\mathcal {I}}$ is happy with respect to ${\mathcal {S}}$ if and only if its corresponding vertex $v \in V(G)$ is happy with respect to S. Therefore, we consider Maximum Happy Set on an interval representation ${\mathcal {I}}$ instead of its original interval graph G. Let $H({\mathcal {I}}{;}{\mathcal {S}})$ be a set of happy intervals with respect to ${\mathcal {S}}\subseteq {\mathcal {I}}$ and our task is to find ${\mathcal {S}}$ such that $|H({\mathcal {I}}{;}{\mathcal {S}})|$ is maximized.

We denote by $\textsf{left}(I_{i})$ and $\textsf{right}(I_{i})$ the left endpoint and the right endpoint of an interval $I_i \in {\mathcal {I}}$, respectively. One can easily transform an interval representation ${\mathcal {I}}$ of G into another one without changing G so that distinct integers between 1 and 2n are assigned to the endpoints $\textsf{left}(I_{i})$ and $\textsf{right}(I_{i})$ of every interval $I_i$. Moreover, we assume that intervals of ${\mathcal {I}}$ are sorted in increasing order of the right endpoints, that is, $\textsf{right}(I_{i}) < \textsf{right}(I_{j})$ for any integers i, j with $1\le i<j \le n$. We then add dummy intervals $I_0$ and $I_{n+1}$ with $\textsf{left}(I_{0}) = -1, \textsf{right}(I_{0}) = 0, \textsf{left}(I_{n+1}) = 2n+1$, and $\textsf{right}(I_{n+1}) = 2n+2$ into ${\mathcal {I}}$. The addition of $I_0$ and $I_{n+1}$ is not essential for proving Theorem 2, but this simplifies the description of our algorithm. In the remainder of this section, we assume that ${\mathcal {I}}$ has $I_0$ and $I_{n+1}$. For an integer $i\in \{0,\ldots ,n+1\}$, we let ${\mathcal {I}}_i = \{I_0, I_1, \ldots , I_i\}$ and $\overline{{\mathcal {I}}_{i}} = {\mathcal {I}}{\setminus } {\mathcal {I}}_i$.

Fig. 4

If $k=2$, the optimal solution of ${\mathcal {I}}_5$ is $\{I_4,I_5\}$, while the optimal solution ${\mathcal {S}}^*$ of ${\mathcal {I}}_6$ and the partial solution ${\mathcal {S}}_5 = {\mathcal {S}}^*\cap {\mathcal {I}}_5$ are $\{I_1, I_2\}$ or $\{I_2, I_3\}$

We describe the idea of our algorithm. Let ${\mathcal {S}}^*$ be a subset of ${\mathcal {I}}\setminus \{I_0, I_{n+1}\}$ such that $|H({\mathcal {I}}{;}{\mathcal {S}}^*)|$ is maximized among all subsets of ${\mathcal {I}}\setminus \{I_0, I_{n+1}\}$ of size k. Since both $I_0$ and $I_{n+1}$ have no intersection with other intervals of ${\mathcal {I}}$, ${\mathcal {S}}^*$ is also the optimal solution of the original interval representation that has no dummy intervals $I_0$ and $I_{n+1}$. In order to find ${\mathcal {S}}^*$, we wish to compute a partial solution ${\mathcal {S}}_i = {\mathcal {S}}^*\cap {\mathcal {I}}_i$ for each $i \in \{0, 1, \ldots , n+1\}$ by means of dynamic programming. Since ${\mathcal {I}} = {\mathcal {I}}_{n+1}$, we have ${\mathcal {S}}^*= {\mathcal {S}}_{n+1}$. Notice that, however, a partial solution ${\mathcal {S}}_i$ is not always equal to an optimal solution of ${\mathcal {I}}_i$ (see Fig. 4 as an example). This indicates that it is not enough to find only an optimal solution of ${\mathcal {I}}_i$ as a partial solution ${\mathcal {S}}_i$. To correctly compute ${\mathcal {S}}_i$ for each $i \in \{0,\ldots , n+1\}$, we guess integers $r,\ell$, and $k^\prime$ that satisfy the following three conditions for ${\mathcal {S}}^*$:

• the interval $I_{r}$ has the largest right endpoint among all intervals in ${\mathcal {I}}_i \setminus {\mathcal {S}}^*$, that is, $I_{r}\notin {\mathcal {S}}^*$ and $\textsf{right}(I_{i^\prime })\le \textsf{right}(I_{r})$ for any $I_{i^\prime } \in {\mathcal {I}}_i {\setminus } {\mathcal {S}}^*$;

• the interval $I_{\ell }$ has the smallest left endpoint among all intervals in $\overline{{\mathcal {I}}_{i}} \setminus {\mathcal {S}}^*$, that is, $I_{\ell }\notin {\mathcal {S}}^*$ and $\textsf{left}(I_{\ell })\le \textsf{left}(I_{i^\prime })$ for any $I_{i^\prime } \in \overline{{\mathcal {I}}_{i}} {\setminus } {\mathcal {S}}^*$; and

• $|{\mathcal {S}}_i| = k^\prime$.

Fig. 5

For the above interval representation ${\mathcal {I}} = \{I_1, I_2 \ldots , I_7\}$, if $k=3$, the optimal solution ${\mathcal {S}}^*$ is $\{I_1, I_2, I_6\}$, which is drawn with dotted line segments. Then, for $i=3$, the interval $I_3$ (resp. $I_5$) has the largest right (resp. the smallest left) endpoint among all intervals in ${\mathcal {I}}_i {\setminus } {\mathcal {S}}^*$ (resp. $\overline{{\mathcal {I}}_{i}} {\setminus } {\mathcal {S}}^*$), and $|{\mathcal {S}}_i| = |{\mathcal {S}}^*\cap {\mathcal {I}}_i| = 2$. Therefore, a quadruple (3, 3, 5, 2) is compatible with ${\mathcal {S}}^*$

We say that a quadruple $(i, r, \ell , k^\prime )$ of integers is compatible with ${\mathcal {S}}^*$ if $i, r, \ell$, and $k^\prime$ satisfy the above three conditions (see Fig. 5). Clearly, if $(i, r, \ell , k^\prime )$ is compatible with ${\mathcal {S}}^*$, then $0\le r\le i < \ell \le n+1$ and $0\le k^\prime \le k$ hold. For integers i, $r$, and $\ell$, let $\overrightarrow{{\mathcal {I}}_{r}}= \{I_{i^\prime } \in {\mathcal {I}}_i \mid \textsf{right}(I_{r}) < \textsf{right}(I_{i^\prime })\}$ and let ${\mathcal {I}}_{i,\ell }$ be a shorthand for ${\mathcal {I}}_i \cup \{I_\ell \}$ (See again Fig. 5 as an example. If $i=3$, we have $\overrightarrow{{\mathcal {I}}_{r}}= \emptyset$ because $r= 3$, and if $i=6$, we have $\overrightarrow{{\mathcal {I}}_{r}}= \{I_6\}$ because $r= 5$). We then obtain the following lemma.

Lemma 4

For an interval representation ${\mathcal {I}}$ and an integer k, let ${\mathcal {S}}^*$ be an optimal solution of ${\mathcal {I}}\setminus \{I_0, I_{n+1}\}$ such that $|{\mathcal {S}}^*| = k$. Suppose that a quadruple $(i, r, \ell , k^\prime )$ of integers is compatible with ${\mathcal {S}}^*$ and ${\mathcal {S}}_i^\prime \subseteq {\mathcal {I}}_{i,\ell } {\setminus } \{I_0,I_r, I_\ell \}$ is an optimal solution of ${\mathcal {I}}_{i, \ell }$ such that $\overrightarrow{{\mathcal {I}}_{r}}\subseteq {\mathcal {S}}_i^\prime$ and $|{\mathcal {S}}_i^\prime | = k^\prime$. Then, there is an optimal solution ${\mathcal {S}}^\star$ of ${\mathcal {I}} {\setminus } \{I_0, I_{n+1}\}$ such that ${\mathcal {S}}_i^\prime = {\mathcal {S}}^\star \cap {\mathcal {I}}_i$.

Proof

Let ${\mathcal {S}}_i = {\mathcal {S}}^*\cap {\mathcal {I}}_i$ and ${\mathcal {S}}^\star = ({\mathcal {S}}^*{\setminus } {\mathcal {S}}_i)\cup {\mathcal {S}}_i^\prime$. Note that $\overline{{\mathcal {I}}_{i}} {\setminus } {\mathcal {S}}^*= \overline{{\mathcal {I}}_{i}} {\setminus } {\mathcal {S}}^\star$ holds. We then show that the following three inequalities:

• (I) $|H({\mathcal {I}}{;}{\mathcal {S}}^*)\cap {\mathcal {I}}_{i,\ell }| \le |H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}}_i)|$;

• (II) $|H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}}_i^\prime )| \le |H({\mathcal {I}}{;}{\mathcal {S}}^\star )\cap {\mathcal {I}}_{i, \ell }|$; and

• (III) $|H({\mathcal {I}}{;}{\mathcal {S}}^*){\setminus } {\mathcal {I}}_{i, \ell }| \le |H({\mathcal {I}}{;}{\mathcal {S}}^\star ){\setminus } {\mathcal {I}}_{i, \ell }|$.

Since $|H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}}_i)| \le |H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}}_i^\prime )|$ from the maximality of ${\mathcal {S}}_i^\prime$, we have $|H({\mathcal {I}}{;}{\mathcal {S}}^*)|$ from the inequalities (I)–(III) as follows:

$$\begin{aligned} |H({\mathcal {I}}{;}{\mathcal {S}}^*)|&= |H({\mathcal {I}}{;}{\mathcal {S}}^*)\cap {\mathcal {I}}_{i, \ell }| + |H({\mathcal {I}}{;}{\mathcal {S}}^*)\setminus {\mathcal {I}}_{i, \ell }|\\&\le |H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}}_i)| + |H({\mathcal {I}}{;}{\mathcal {S}}^\star )\setminus {\mathcal {I}}_{i, \ell }| \\&\le |H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}}_i^\prime )| + |H({\mathcal {I}}{;}{\mathcal {S}}^\star )\setminus {\mathcal {I}}_{i, \ell }| \\&\le |H({\mathcal {I}}{;}{\mathcal {S}}^\star )\cap {\mathcal {I}}_{i, \ell }| + |H({\mathcal {I}}{;}{\mathcal {S}}^\star )\setminus {\mathcal {I}}_{i, \ell }| \\&= |H({\mathcal {I}}{;}{\mathcal {S}}^{\star })|. \end{aligned}$$

Namely, ${\mathcal {S}}^\star$ is also the optimal solution of ${\mathcal {I}} \setminus \{I_0, I_{n+1}\}$ from the maximality of $|H({\mathcal {I}}{;}{\mathcal {S}}^*)|$.

We first show the inequality (I). Consider an interval representation ${\mathcal {I}}$ of an interval graph G on Lemma 3, and set ${\mathcal {I}}^\prime = {\mathcal {I}}{\setminus } {\mathcal {I}}_{i,\ell }$ and ${\mathcal {S}} = {\mathcal {S}}^*$. Then, we have

$$\begin{aligned} H({\mathcal {I}}{;}{\mathcal {S}}^*) \cap {\mathcal {I}}_{i,\ell }&= H({\mathcal {I}}{;}{\mathcal {S}}^*) \setminus {\mathcal {I}}^\prime \\&\subseteq H({\mathcal {I}}\setminus {\mathcal {I}}^\prime {;}{\mathcal {S}}^*\setminus {\mathcal {I}}^\prime ) \\&= H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}}^*\cap {\mathcal {I}}_{i,\ell }). \end{aligned}$$

Since ${\mathcal {S}}_i = {\mathcal {S}}^*\cap {\mathcal {I}}_i$ and $I_\ell \notin {\mathcal {S}}^*$, we have $|H({\mathcal {I}}{;}{\mathcal {S}}^*)\cap {\mathcal {I}}_{i, \ell }| \le |H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}}^*\cap {\mathcal {I}}_{i,\ell })| = |H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}}_i)|$.

We next show the inequality (II). Consider an interval $I_j \in H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}}_i^\prime )$. Then, $I_j \in {\mathcal {S}}_i^\prime$ and $I_j$ intersects with none of intervals in ${\mathcal {I}}_{i,\ell }{\setminus } {\mathcal {S}}_i^\prime = {\mathcal {I}}_{i,\ell }{\setminus } ({\mathcal {S}}^\star \cap {\mathcal {I}}_{i}) = {\mathcal {I}}_{i,\ell }{\setminus } {\mathcal {S}}^\star$. In particular, $\textsf{right}(I_{j}) < \textsf{left}(I_{\ell })$ holds. For any interval $I_{j^\prime } \in \overline{{\mathcal {I}}_{i}} {\setminus } {\mathcal {S}}^*$, equivalently $I_{j^\prime } \in \overline{{\mathcal {I}}_{i}} {\setminus }{\mathcal {S}}^\star$, we also have $\textsf{left}(I_{\ell }) \le \textsf{left}(I_{j^\prime })$ from the definition of $I_{\ell }$. Thus, $\textsf{right}(I_{j}) < \textsf{left}(I_{j^\prime })$ holds and $I_j$ has no intersection with $I_{j^\prime }$. As a consequence, $I_j$ intersects with none of intervals in ${\mathcal {I}}{\setminus } {\mathcal {S}}^\star$, that is, $I_j \in H({\mathcal {I}}{;}{\mathcal {S}}^\star )\cap {\mathcal {I}}_{i, \ell }$. This means that $|H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}}_i^\prime )| \le |H({\mathcal {I}}{;}{\mathcal {S}}^\star )\cap {\mathcal {I}}_{i, \ell }|$.

Finally, we show the inequality (III). Consider an interval $I_j \in H({\mathcal {I}}{;}{\mathcal {S}}^*) {\setminus } {\mathcal {I}}_{i, \ell }$. Then, $I_j \in {\mathcal {S}}^*{\setminus } {\mathcal {I}}_{i,\ell }$ and $I_j$ intersects with none of intervals in ${\mathcal {I}}\setminus {\mathcal {S}}^*$. In particular, $\textsf{right}(I_{r}) < \textsf{left}(I_{j})$ holds. Recall that $\overline{{\mathcal {I}}_{i}} {\setminus } {\mathcal {S}}^*= \overline{{\mathcal {I}}_{i}} {\setminus } {\mathcal {S}}^\star$. This means that $I_j \in {\mathcal {S}}^\star {\setminus } {\mathcal {I}}_{i,\ell }$ and $I_j$ intersects with none of intervals in $\overline{{\mathcal {I}}_{i}} \setminus {\mathcal {S}}^\star$. Moreover, from the assumptions that $\overrightarrow{{\mathcal {I}}_{r}}\subseteq {\mathcal {S}}_i^\prime$ and ${\mathcal {S}}^\star = ({\mathcal {S}}^*{\setminus } {\mathcal {S}}_i)\cup {\mathcal {S}}_i^\prime$, it holds that $\textsf{right}(I_{j^\prime })\le \textsf{right}(I_{r})$ for any interval $I_{j^\prime }$ in ${\mathcal {I}}_i {\setminus } {\mathcal {S}}_i^\prime = {\mathcal {I}}_i {\setminus } {\mathcal {S}}^\star$. Combined with $\textsf{right}(I_{r}) < \textsf{left}(I_{j})$, we have $\textsf{right}(I_{j^\prime }) < \textsf{left}(I_{j})$, that is, $I_j$ has no intersection with $I_{j^\prime } \in {\mathcal {I}}_i {\setminus } {\mathcal {S}}^\star$. Therefore, $I_j$ intersects with none of intervals in ${\mathcal {I}}\setminus {\mathcal {S}}^\star$ and thus $I_j \in H({\mathcal {I}}{;}{\mathcal {S}}^\star ) {\setminus } {\mathcal {I}}_{i,\ell }$. We conclude that $|H({\mathcal {I}}{;}{\mathcal {S}}^*){\setminus } {\mathcal {I}}_{i, \ell }| \le |H({\mathcal {I}}{;}{\mathcal {S}}^\star ){\setminus } {\mathcal {I}}_{i, \ell }|$. $\square$

Lemma 4 suggests that, in order to compute a partial solution of ${\mathcal {I}}_i$ for each $i \in \{0,\ldots ,n\}$, it suffices to guess a quadruple $(i, r, \ell , k^\prime )$ of integers that is compatible with ${\mathcal {S}}^*$ and find ${\mathcal {S}}$ such that $|H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}})|$ is the maximum among all subsets ${\mathcal {S}} \subseteq {\mathcal {I}}_{i, \ell }{\setminus } \{I_0, I_r, I_{\ell }\}$ that satisfies $\overrightarrow{{\mathcal {I}}_{r}}\subseteq {\mathcal {S}}$ and $|{\mathcal {S}}| = k^\prime$.

4.1 Algorithm

Our algorithm employs the following main function $f({\mathcal {I}}_{i,\ell }{;} r, k^\prime )$ and the subfunction $f_\textrm{max}({\mathcal {I}}_{i,\ell }{;} k^\prime )$, where $i,r, \ell$, and $k^\prime$ are integers such that $0\le i<\ell \le n+1$, $\max \{0, i-k^\prime \}\le r\le i$, and $0\le k^\prime \le k$;

• $f({\mathcal {I}}_{i,\ell }{;} r, k^\prime )$ returns the maximum of $|H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}})|$ among all subsets ${\mathcal {S}}\subseteq {\mathcal {I}}_{i,\ell } {\setminus } \{I_0,I_r, I_\ell \}$ such that $\overrightarrow{{\mathcal {I}}_{r}}\subseteq {\mathcal {S}}$ and $|{\mathcal {S}}| = k^\prime$;

• $f_\textrm{max}({\mathcal {I}}_{i,\ell }{;} k^\prime )$ returns the maximum of $|H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}})|$ among all subsets ${\mathcal {S}} \subseteq {\mathcal {I}}_{i,\ell }{\setminus } \{I_0,I_{\ell } \}$ such that $|{\mathcal {S}}| = k^\prime$.

We let $f({\mathcal {I}}_{i,\ell }{;} r, k^\prime ) = -\infty$ and $f_\textrm{max}({\mathcal {I}}_{i,\ell }{;} k^\prime ) = -\infty$ if there exists no subset ${\mathcal {S}}$ that satisfies all the prescribed conditions for $f$ and $f_\textrm{max}$, respectively. We remark that the integer $r$ must be at least $i-k^\prime$; otherwise it implies $|{\mathcal {S}}| > k^\prime$ and violates the condition $|{\mathcal {S}}| = k^\prime$. We will compute values $f({\mathcal {I}}_{i,\ell }{;} r, k^\prime )$ and $f_\textrm{max}({\mathcal {I}}_{i,\ell }{;} k^\prime )$ by means of dynamic programming in accordance with the lexicographical order of a quadruple $(i, r, \ell , k^\prime )$. We lastly obtain the value $f_\textrm{max}({\mathcal {I}}_{n,n+1}{;} k)$, which is the maximum size of $H({\mathcal {I}}{;}{\mathcal {S}})$ such that ${\mathcal {S}}\subseteq {\mathcal {I}}\setminus \{I_0,I_{n+1}\}$ and $|{\mathcal {S}}| = k$.

For each triple $(i,\ell , k^\prime )$ of integers, it is easy to see that $f_\textrm{max}({\mathcal {I}}_{i,\ell }{;} k^\prime )$ is obtained as follows:

$$\begin{aligned} f_\textrm{max}({\mathcal {I}}_{i,\ell }{;} k^\prime ) = \max _{\max \{0, i-k^\prime \}\le r\le i} f({\mathcal {I}}_{i,\ell }{;} r, k^\prime ). \end{aligned}$$

We compute $f({\mathcal {I}}_{i,\ell }{;} r, k^\prime )$ by dividing two cases (i) $r< i$ and (ii) $r= i$.

Case (i): $\varvec{r< i}$ 

If $i = 0$, then we have $f({\mathcal {I}}_{i,\ell }{;} r, k^\prime ) = -\infty$ because there exists no integer $r$ such that $\max \{0, i-k^\prime \}\le r< i$. If $k^\prime = 0$, then we also have $f({\mathcal {I}}_{i,\ell }{;} r, k^\prime ) = -\infty$ for any i, $\ell$, and $r$ because there is no subset ${\mathcal {S}}$ such that $I_i \in {\mathcal {S}}$ and $|{\mathcal {S}}| = 0$.

Suppose that $i>0$ and $k^\prime >0$. Let ${\mathcal {S}}$ be a subset of ${\mathcal {I}}_{i,\ell } \setminus \{I_0,I_r, I_\ell \}$ such that $\overrightarrow{{\mathcal {I}}_{r}}\subseteq {\mathcal {S}}$, $|{\mathcal {S}}| = k^\prime$, and $|H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}})|$ is maximized. Especially, $I_i \in {\mathcal {S}}$ in this case. From Lemma 3, it holds that $H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}}){\setminus } \{I_i\} = H({\mathcal {I}}_{i-1, \ell }{;}{\mathcal {S}} {\setminus } \{I_i\})$. We thus compute $f({\mathcal {I}}_{i,\ell }{;} r, k^\prime )$ from $f({\mathcal {I}}_{i-1,\ell }{;} r, k^{\prime }-1)$ by deciding whether the interval $I_i$ is happy with respect to ${\mathcal {S}}$. If $I_i$ intersects with the interval $I_r\notin {\mathcal {S}}$ or $I_\ell \notin {\mathcal {S}}$, then $I_i$ is unhappy. Conversely, assume that $I_i$ intersects with neither $I_r$ nor $I_\ell$. Let ${\mathcal {I}}_{i,\ell }^\prime$ be a set of intervals of ${\mathcal {I}}_{i, \ell }$ that intersect with $I_i$. Since the intervals of ${\mathcal {I}}_{i,\ell }$ are sorted in increasing order of the right endpoints, we have ${\mathcal {I}}_{i,\ell }^\prime \subseteq \overrightarrow{{\mathcal {I}}_{r}}$ from the definition of $I_r$. Combined with $\overrightarrow{{\mathcal {I}}_{r}}\subseteq {\mathcal {S}}$, we have ${\mathcal {I}}_{i,\ell }^\prime \subseteq {\mathcal {S}}$ and hence $I_i$ is happy. Therefore, it suffices to check that $I_i$ intersects with $I_r$ or $I_\ell$ to decide whether $I_i$ is happy, and we have

$$\begin{aligned} f({\mathcal {I}}_{i,\ell }{;} r, k^\prime ) = {\left\{ \begin{array}{ll} f({\mathcal {I}}_{i-1,\ell }{;} r, k^{\prime }-1) &{}{}\quad \text{ if }\, I_i\cap I_r\ne \emptyset \text{ or } I_i\cap I_\ell \ne \emptyset ,\\ f({\mathcal {I}}_{i-1,\ell }{;} r, k^{\prime }-1) +1&{}{}\quad \text{ otherwise. } \end{array}\right. } \end{aligned}$$

Case (ii): $\varvec{r= i}$ 

If $i = 0$, an interval representation ${\mathcal {I}}_{i,\ell }$ consists of the two disjoint intervals $I_0$ and $I_\ell$. Only $S = \emptyset$ satisfies the prescribed conditions for $f({\mathcal {I}}_{i,\ell }{;} i, k^\prime )$. Thus, for any integer $\ell > 0$, we have $f({\mathcal {I}}_{i,\ell }{;} i, k^\prime ) = 0$ if $k^\prime =0$; otherwise $f({\mathcal {I}}_{i,\ell }{;} i, k^\prime ) = -\infty$. Suppose that $i>0$. To calculate $f({\mathcal {I}}_{i,\ell }{;} i, k^\prime )$ for each integers $i, \ell$, and $k^\prime$, we give the following lemma.

Lemma 5

Let ${\mathcal {S}}$ be a subset of ${\mathcal {I}}_{i,\ell } {\setminus } \{I_0,I_i,I_\ell \}$ such that $|{\mathcal {S}}| = k^\prime$. In addition, let $\ell ^\prime \in \{i, \ell \}$ be an integer such that $\textsf{left}(I_{\ell ^\prime }) \le \min \{\textsf{left}(I_{i}), \textsf{left}(I_{\ell })\}$. Then, $H({\mathcal {I}}_{i, \ell }{;}{\mathcal {S}}) = H({\mathcal {I}}_{i-1, \ell ^\prime }{;}{\mathcal {S}})$.

Proof

We first show that $H({\mathcal {I}}_{i, \ell }{;}{\mathcal {S}}) \subseteq H({\mathcal {I}}_{i-1, \ell ^\prime }{;}{\mathcal {S}})$. Let $I^\prime \in \{I_i, I_\ell \}$ be the other interval that is distinct from $I_{\ell ^\prime }$. Since $I^\prime \notin {\mathcal {S}}$, we have $H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}}) = H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}}) {\setminus } \{I^\prime \}$. Moreover, from Lemma 3, it holds that

$$\begin{aligned} H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}}) \setminus \{I^\prime \} \subseteq H({\mathcal {I}}_{i,\ell } \setminus \{I^\prime \}{;}{\mathcal {S}} \setminus \{I^\prime \}) = H({\mathcal {I}}_{i-1, \ell ^\prime }{;}{\mathcal {S}}). \end{aligned}$$

Thus, we have $H({\mathcal {I}}_{i, \ell }{;}{\mathcal {S}}) \subseteq H({\mathcal {I}}_{i-1, \ell ^\prime }{;}{\mathcal {S}})$.

We next show that $H({\mathcal {I}}_{i-1, \ell ^\prime }{;}{\mathcal {S}}) \subseteq H({\mathcal {I}}_{i, \ell }{;}{\mathcal {S}})$. Since $I_{\ell ^\prime } \notin {\mathcal {S}}$, we have $\textsf{right}(I_{j}) < \textsf{left}(I_{\ell ^\prime })$ for any interval $I_j \in H({\mathcal {I}}_{i-1, \ell ^\prime }{;}{\mathcal {S}})$. In addition, $\textsf{left}(I_{\ell ^\prime }) \le \min \{\textsf{left}(I_{i}), \textsf{left}(I_{\ell })\}$ holds from the definition of $I_{\ell ^\prime }$. Therefore, $I_j$ intersects with neither $I_i$ nor $I_\ell$, which implies that $I_j \in H({\mathcal {I}}_{i,\ell }{;}{\mathcal {S}})$. We conclude that $H({\mathcal {I}}_{i-1, \ell ^\prime }{;}{\mathcal {S}}) \subseteq H({\mathcal {I}}_{i, \ell }{;}{\mathcal {S}})$. $\square$

Lemma 5 immediately leads to the following equation:

$$\begin{aligned} f({\mathcal {I}}_{i,\ell }{;} i, k^\prime ) = {\left\{ \begin{array}{ll} f_\textrm{max}({\mathcal {I}}_{i-1,i}{;} k^{\prime }) &{}\quad \text {if}\, \textsf{left}(I_{i}) < \textsf{left}(I_{\ell }),\\ f_\textrm{max}({\mathcal {I}}_{i-1,\ell }{;} k^{\prime }) &{}\quad \text {otherwise.} \end{array}\right. } \end{aligned}$$

4.2 Running Time

We bound the running time of our algorithm for interval graphs. Given an n-vertex interval graph G and an integer k, we first convert G to its interval representation ${\mathcal {I}}$ in linear time and add the dummy intervals $I_0$ and $I_{n+1}$. Recall that each endpoint of intervals can be assigned to an integer between $-1$ to $2n+2$. We can sort intervals of ${\mathcal {I}}$ in increasing order of their right endpoints by an O(n)-time integer sorting algorithm. For each integer $i \in \{0,\ldots , n+1\}$, we compute ${\mathcal {I}}_i$ and $\overline{{\mathcal {I}}_{i}}$ in $O(n^2)$ time.

We then compute values $f({\mathcal {I}}_{i,\ell }{;} r, k^\prime )$ and $f_\textrm{max}({\mathcal {I}}_{i,\ell }{;} k^\prime )$ for each integers $i,r,\ell$, and $k^\prime$ with $0\le i<\ell \le n+1$, $\max \{0, i-k^\prime \}\le r\le i$, and $0\le k^\prime \le k$. In fact, for each i, the interval $I_\ell$ can be chosen from a set ${\mathcal {I}}^\prime \subseteq \overline{{\mathcal {I}}_{i}}$ of size at most $k+1$, where ${\mathcal {I}}^\prime$ consists of the first $k+1$ intervals of $\overline{{\mathcal {I}}_{i}}$ sorted in increasing order of their left endpoints; otherwise, from the definition of $I_\ell$, an optimal solution ${\mathcal {S}}^*$ of ${\mathcal {I}}$ has size at least $k+1$, a contradiction.

Let $(i, r, \ell , k^\prime )$ be a quadruple of integers. In the case of $r< i$, our algorithm computes $f({\mathcal {I}}_{i,\ell }{;} r, k^\prime )$ in O(1) time by checking whether $I_i\cap I_r\ne \emptyset$ or $I_i\cap I_\ell \ne \emptyset$. In the case of $r= i$, our algorithm computes $f({\mathcal {I}}_{i,\ell }{;} i, k^\prime )$ in O(1) time by checking whether $\textsf{left}(I_{i}) < \textsf{left}(I_{\ell })$. Thus, for all quadruples $(i, r, \ell , k^\prime )$, the value in each case can be computed in $O(k^3n)$ time. Obviously, for all triples $(i,\ell ,k^\prime )$, $f_\textrm{max}({\mathcal {I}}_{i,\ell }{;} k^\prime )$ can be computed in $O(k^3n)$ time.

Finally, by taking the value $f_\textrm{max}({\mathcal {I}}_{n,n+1}{;} k)$ in O(1) time, we determine the maximum number of happy vertices for the given interval graph G and integer k. The total running time of our algorithm is $O(n^2 +k^3n)$, as claimed in Theorem 2. $\square$

5 Extension of Algorithmic Techniques

In this section, we demonstrate that our idea for interval graphs is applicable to other subclasses of co-comparability graphs.

5.1 Permutation Graphs

Let $\pi = (\pi (1), \pi (2), \ldots , \pi (n))$ be a permutation of the integers from 1 to n. We denote by $\pi ^{-1}(i)$ the position of the number i in $\pi$. Consider two horizontal parallel lines on the plane, where the upper line has distinct n points labeled $1,2,\ldots , n$, and the lower line has distinct n points labeled $\pi (1),\pi (2),\ldots , \pi (n)$ in the order from left to right, respectively. For each integer $i \in \{1,2,\ldots , n\}$, let $L_i$ be a line segment from a label i on the upper line to a label i on the lower line. A graph $G = (V,E)$ with vertices $v_1, v_2, \ldots , v_n$ is called a permutation graph if there exists a permutation $\pi$ between 1 and n such that for any two distinct integers $i,j \in \{1,\ldots ,n\}$, $v_iv_j \in E$ if and only if $L_i$ intersects with $L_j$. A set ${\mathcal {L}}$ of line segments corresponding to G is called a line representation of G. We illustrate an example of the line representation and its corresponding permutation graph in Fig. 6.

Theorem 6

Given an n-vertex permutation graph G and a non-negative integer k, Maximum Happy Set is solvable in $O(n^2 + k^3n)$ time.

Fig. 6

a The line representation and b its corresponding permutation graph, where $\pi = (4,2,5,1,3)$

The algorithmic approach for permutation graphs is basically the same as for interval graphs in Sect. 4. Given a permutation graph G, a line representation ${\mathcal {L}}$ of G can be constructed in linear time [13]. We say that a line segment $L \in {\mathcal {L}}$ is happy with respect to ${\mathcal {S}}$ if $L^\prime \in {\mathcal {S}}$ for every line segment $L^\prime$ such that $L \cap L^\prime \ne \emptyset$. Maximum Happy Set on ${\mathcal {L}}$ is the problem of finding ${\mathcal {S}} \subseteq {\mathcal {L}}$ such that the size of a set $H({\mathcal {L}}{;}{\mathcal {S}})$ of happy line segments with respect to ${\mathcal {S}}$ is maximized. We add a dummy line segment $L_0$ (resp. $L_{n+1}$) that connects a label 0 (resp. $n+1$) on the upper line and a label $\pi (0)= 0$ (resp. $\pi (n+1) = n+1$) on the lower line. Both $L_0$ and $L_{n+1}$ intersect with none of the other line segments in ${\mathcal {L}}$. For an integer $i\in \{0,\ldots ,n+1\}$, we let ${\mathcal {L}}_i = \{L_0, L_1, \ldots , L_i\}$ and $\overline{{\mathcal {L}}_{i}} = {\mathcal {L}}{\setminus } {\mathcal {L}}_i$.

Let ${\mathcal {S}}^*$ be an optimal solution for ${\mathcal {L}}$ and let ${\mathcal {S}}_i = {\mathcal {S}}^*\cap {\mathcal {L}}_i$. To characterize a partial solution ${\mathcal {S}}_i$ of ${\mathcal {L}}_i$, we seek integers $r, \ell$, and $k^\prime$ that satisfy the following three conditions for ${\mathcal {S}}^*$:

• $L_{r} \in {\mathcal {L}}_i \setminus {\mathcal {S}}^*$ and $\pi ^{-1}(i^\prime )\le \pi ^{-1}(r)$ for any $L_{i^\prime } \in {\mathcal {L}}_i {\setminus } {\mathcal {S}}^*$;

• $L_{\ell } \in \overline{{\mathcal {L}}_{i}} \setminus {\mathcal {S}}^*$ and $\pi ^{-1}(\ell )\le \pi ^{-1}(i^\prime )$ for any $L_{i^\prime } \in \overline{{\mathcal {L}}_{i}} {\setminus } {\mathcal {S}}^*$; and

• $|{\mathcal {S}}_i| = k^\prime$.

Fig. 7

For the above line representation ${\mathcal {L}} = \{L_1, L_2 \ldots , L_6\}$, if $k=3$, the optimal solution ${\mathcal {S}}^*$ is $\{L_1, L_4, L_6\}$, which is drawn with dotted line segments. For $i=4$, ${\mathcal {L}}_i {\setminus } {\mathcal {S}}^*= \{L_2, L_3\}$ with $\pi ^{-1}(3) < \pi ^{-1}(2)$, $\overline{{\mathcal {L}}_{i}} \setminus {\mathcal {S}}^*= \{L_5\}$, and $|{\mathcal {S}}_i| = |{\mathcal {S}}^*\cap {\mathcal {L}}_i| = 2$. Thus, a quadruple (4, 2, 5, 2) is compatible with ${\mathcal {S}}^*$

We say that a quadruple $(i, r, \ell , k^\prime )$ of integers is compatible with ${\mathcal {S}}^*$ if $i, r, \ell$, and $k^\prime$ satisfy the above three conditions (see Fig. 7). For integers i, $r$, and $\ell$, let ${\mathcal {L}}_{i,\ell }$ be a shorthand for ${\mathcal {L}}_i \cup \{L_\ell \}$ and let $\overrightarrow{{\mathcal {L}}_{r}}= \{L_{i^\prime } \in {\mathcal {L}}_i \mid \pi ^{-1}(r) < \pi ^{-1}(i^\prime )\}$. For example, if $i=4$ in Fig. 7, we have $\overrightarrow{{\mathcal {L}}_{r}}= \{L_1, L_4\}$ because $r= 2$. Analogous to Lemma 4, we give the following lemma.

Lemma 7

For a line representation ${\mathcal {L}}$ and an integer k, let ${\mathcal {S}}^*$ be an optimal solution of ${\mathcal {L}}\setminus \{L_0, L_{n+1}\}$ such that $|{\mathcal {S}}^*| = k$. Suppose that a quadruple $(i, r, \ell , k^\prime )$ of integers is compatible with ${\mathcal {S}}^*$ and ${\mathcal {S}}_i^\prime \subseteq {\mathcal {L}}_{i,\ell } {\setminus } \{L_0,L_r, L_\ell \}$ is an optimal solution of ${\mathcal {L}}_{i, \ell }$ such that $\overrightarrow{{\mathcal {L}}_{r}}\subseteq {\mathcal {S}}_i^\prime$ and $|{\mathcal {S}}_i^\prime | = k^\prime$. Then, there is an optimal solution ${\mathcal {S}}^\star$ of ${\mathcal {L}} {\setminus } \{L_0, L_{n+1}\}$ such that ${\mathcal {S}}_i^\prime = {\mathcal {S}}^\star \cap {\mathcal {L}}_i$.

Proof

We replace the words and notations in the proof of Lemma 4 as follows:

• an interval I $\rightarrow$ a line segment L;

• an interval representation ${\mathcal {I}}$ $\rightarrow$ a line representation ${\mathcal {L}}$; and

• $\textsf{left}$ and $\textsf{right}$ $\rightarrow$ $\pi ^{-1}$.

One can verify the correctness of Lemma 7 by the proof after replacing them. $\square$

5.1.1 Algorithm

Given a line representation ${\mathcal {L}}$ and an integer k, suppose that $i,r,\ell$, and $k^\prime$ are integers such that $0 \le r\le i < \ell \le n+1$ and $0\le k^\prime \le k$. Our algorithm for permutation graphs employs the following three functions:

• $g_{\textrm{in}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime )$ returns the maximum of $|H({\mathcal {L}}_{i, \ell }{;}{\mathcal {S}})|$ among all subsets ${\mathcal {S}}\subseteq {\mathcal {L}}_{i, \ell } {\setminus } \{L_0, L_r, L_\ell \}$ such that $\overrightarrow{{\mathcal {L}}_{r}}\cup \{L_i\} \subseteq {\mathcal {S}}$ and $|{\mathcal {S}}| = k^\prime$;

• $g_{\textrm{out}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime )$ returns the maximum of $|H({\mathcal {L}}_{i, \ell }{;}{\mathcal {S}})|$ among all subsets ${\mathcal {S}}\subseteq {\mathcal {L}}_{i, \ell } {\setminus } \{L_0, L_r, L_i, L_\ell \}$ such that $\overrightarrow{{\mathcal {L}}_{r}}\subseteq {\mathcal {S}}$ and $|{\mathcal {S}}| = k^\prime$; and

• $g_\textrm{max}({\mathcal {L}}_{i, \ell }{;} k^\prime )$ returns the maximum of $|H({\mathcal {L}}_{i, \ell }{;}{\mathcal {S}})|$ among all subsets ${\mathcal {S}} \subseteq {\mathcal {L}}_{i, \ell }{\setminus } \{L_0,L_{\ell } \}$ such that $|{\mathcal {S}}| = k^\prime$.

If there exists no subset ${\mathcal {S}}$ that satisfies the prescribed conditions, we set $g_{\textrm{in}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime ) = -\infty$, $g_{\textrm{out}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime ) = -\infty$, and $g_\textrm{max}({\mathcal {L}}_{i, \ell }{;} k^\prime ) = -\infty$. It is easy to see that a value $g_\textrm{max}({\mathcal {L}}_{i, \ell }{;} k^\prime )$ can be obtained as follows:

$$\begin{aligned} g_\textrm{max}({\mathcal {L}}_{i, \ell }{;} k^\prime ) = \max _{0\le r\le i}\{g_{\textrm{in}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime ), g_{\textrm{out}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime )\}. \end{aligned}$$

In the remainder of this subsection, we will explain the computation of the functions $g_{\textrm{in}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime )$ and $g_{\textrm{out}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime )$.

Fig. 8

The line representations of the case where $\pi ^{-1}(i) < \pi ^{-1}(r)$ and a $\pi ^{-1}(i-1) > \pi ^{-1}(r)$, b $\pi ^{-1}(i-1) = \pi ^{-1}(r)$, and c $\pi ^{-1}(i-1) < \pi ^{-1}(r)$, respectively

Computation of the function ${g_\textrm{in}}$: If $i=0$, we have $g_{\textrm{in}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime ) = -\infty$ for any $r, \ell$, and $k^\prime$ because there exists no subset ${\mathcal {S}}\subseteq {\mathcal {L}}_{i, \ell }$ that satisfies $L_i \in {\mathcal {S}}$ and $L_0 \notin {\mathcal {S}}$. Similarly, if $i=r$, we have $g_{\textrm{in}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime ) = -\infty$ for any $r, \ell$, and $k^\prime$; and if $k^\prime =0$, we have $g_{\textrm{in}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime ) = -\infty$ for any $i, r$, and $\ell$. In the remainder of this subsection, we suppose that $i > 0, i\ne r$, and $k^\prime >0$.

Let ${\mathcal {S}}$ be a subset of ${\mathcal {L}}_{i, \ell } {\setminus } \{L_0, L_r, L_\ell \}$ such that $|H({\mathcal {L}}_{i,\ell }{;}{\mathcal {S}})|$ is the maximum among all subsets ${\mathcal {S}}\subseteq {\mathcal {L}}_{i, \ell } {\setminus } \{L_0, L_r, L_\ell \}$ with $\overrightarrow{{\mathcal {L}}_{r}}\cup \{L_i\} \subseteq {\mathcal {S}}$ and $|{\mathcal {S}}| = k^\prime$. From Lemma 3, it holds that $H({\mathcal {L}}_{i, \ell }{;}{\mathcal {S}}){\setminus } \{L_i\} = H({\mathcal {L}}_{i-1, \ell }{;}{\mathcal {S}} {\setminus } \{L_i\})$. We thus take values $g_{\textrm{in}}({\mathcal {L}}_{i-1, \ell }{;} r, k^\prime -1)$ and $g_{\textrm{out}}({\mathcal {L}}_{i-1, \ell }{;} r, k^\prime -1)$ to compute $g_{\textrm{in}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime )$. However, $L_i$ may be unhappy with respect to ${\mathcal {S}}$. To determine whether $L_i\in H({\mathcal {L}}_{i, \ell }{;}{\mathcal {S}})$, we consider whether $L_i$ intersects with $L_r$ or $L_\ell$. If $L_i$ intersects with $L_r$ or $L_\ell$, then $L_i$ is clearly unhappy. Conversely, suppose that $L_i$ intersects with neither $L_r$ nor $L_\ell$. Let ${\mathcal {L}}_{i,\ell }^\prime$ be a set of line segments of ${\mathcal {L}}_{i, \ell }$ that intersect with $L_i$. Then, $\pi ^{-1}(i) < \pi ^{-1}(j)$ holds for any $L_{j} \in {\mathcal {L}}_{i,\ell }^\prime$. Since $L_i$ does not intersect with $L_r$, we have $\pi ^{-1}(r) < \pi ^{-1}(i)$ and hence ${\mathcal {L}}_{i,\ell }^\prime \subseteq \overrightarrow{{\mathcal {L}}_{r}}\subseteq {\mathcal {S}}$ holds from the definition of $L_{r}$, which means that $L_i$ is happy. Thus, to determine that $L_i$ is happy, it suffice to confirm whether $L_i$ intersects with $L_r$ or $L_\ell$.

In addition, we must pay attention to whether $L_{i-1} \in {\mathcal {S}}$ or not to compute $g_{\textrm{in}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime )$ (see also Fig. 8). If $\pi ^{-1}(i-1) > \pi ^{-1}(r)$, then $L_{i-1} \in \overrightarrow{{\mathcal {L}}_{r}}$ and hence $L_{i-1} \in {\mathcal {S}}$. We thus have $g_{\textrm{in}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime )$ from $g_{\textrm{in}}({\mathcal {L}}_{i-1, \ell }{;} r, k^\prime -1)$. If $\pi ^{-1}(i-1) = \pi ^{-1}(r)$, then we take $g_{\textrm{out}}({\mathcal {L}}_{i-1, \ell }{;} r, k^\prime -1)$ because $L_{i-1} = L_r$ and $L_r\notin {\mathcal {S}}$. If $\pi ^{-1}(i-1) < \pi ^{-1}(r)$, then we compare values $g_{\textrm{in}}({\mathcal {L}}_{i-1, \ell }{;} r, k^\prime -1)$ and $g_{\textrm{out}}({\mathcal {L}}_{i-1, \ell }{;} r, k^\prime -1)$, and take the larger one. In summary, we obtain the following formula:

$$\begin{aligned}&g_{\textrm{in}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime ) = \\&\qquad {\left\{ \begin{array}{ll} g_{\textrm{in}}({\mathcal {L}}_{i-1, \ell }{;} r, k^{\prime }-1) + c&{}\quad \text {if}\, \pi ^{-1}(i-1) > \pi ^{-1}(r), \\ g_{\textrm{out}}({\mathcal {L}}_{i-1, \ell }{;} r, k^{\prime }-1) + c&{}\quad \text {if}\, \pi ^{-1}(i-1) = \pi ^{-1}(r),\text { and} \\ \max \{ g_{\textrm{in}}({\mathcal {L}}_{i-1, \ell }{;} r, k^{\prime }-1), \\ g_{\textrm{out}}({\mathcal {L}}_{i-1, \ell }{;} r, k^{\prime }-1) \} + c &{}\quad \text {otherwise,} \end{array}\right. } \end{aligned}$$

where

$$\begin{aligned}&c = {\left\{ \begin{array}{ll} 0 &{}{}\quad \text{ if }\, L_{i} \cap L_{r} \ne \emptyset \text{ or } L_{i} \cap L_{\ell } \ne \emptyset \\ 1 &{}{}\quad \text{ otherwise. } \\ \end{array}\right. } \end{aligned}$$

Computation of the function ${g_\textrm{out}}$: Suppose that $i=0$. As in Case (ii) of Sect. 4.1, for any integer $\ell > 0$, we have $g_{\textrm{out}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime ) = 0$ if $r= 0$ and $k^\prime =0$; otherwise $g_{\textrm{out}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime ) = -\infty$. For $i > 0$, we give the following lemma, which can be proved in the same way as the proof of Lemma 5.

Lemma 8

Let ${\mathcal {S}}$ be a subset of ${\mathcal {L}}_{i,\ell } {\setminus } \{L_0,L_r, L_i,L_\ell \}$ such that $|{\mathcal {S}}| = k^\prime$. In addition, let $\ell ^\prime \in \{i, \ell \}$ be an integer such that $\pi ^{-1}(\ell ^\prime ) \le \min \{\pi ^{-1}(i), \pi ^{-1}(\ell )\}$. Then, $H({\mathcal {L}}_{i, \ell }{;}{\mathcal {S}}) = H({\mathcal {L}}_{i-1, \ell ^\prime }{;}{\mathcal {S}})$.

It should be noted that, in contrast to the case for interval graphs, $L_i \notin {\mathcal {S}}$ does not always mean $r= i$. It is guaranteed that $\pi ^{-1}(i) \le \pi ^{-1}(r)$; otherwise, $L_i \in {\mathcal {S}}$, contradicting the condition of $g_\textrm{out}$. Therefore, in addition to whether $\pi ^{-1}(i) < \pi ^{-1}(\ell )$ or not, the relationship between i, $i-1$, and $r$ must also be carefully considered (see again Fig. 8). We have

$$\begin{aligned}&g_{\text {out}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime ) = \\ {}&{\left\{ \begin{array}{ll} g_\text {max}({\mathcal {L}}_{i-1, \ell ^\prime }{;} k^{\prime }) &{}{}\quad \text{ if }\, \pi ^{-1}(i) = \pi ^{-1}(r),\\ g_{\text {in}}({\mathcal {L}}_{i-1, \ell ^\prime }{;} r, k^{\prime })&{}{}\quad \text{ if }\, \pi ^{-1}(i)< \pi ^{-1}(r) \text{ and } \pi ^{-1}(i-1) > \pi ^{-1}(r), \\ g_{\text {out}}({\mathcal {L}}_{i-1, \ell ^\prime }{;} r, k^{\prime })&{}{}\quad \text{ if }\, \pi ^{-1}(i) < \pi ^{-1}(r) \text{ and } \pi ^{-1}(i-1) = \pi ^{-1}(r), \, \text{ and }\, \\ \max \{ g_{\text {in}}({\mathcal {L}}_{i-1, \ell ^\prime }{;} r, k^{\prime }), \\ g_{\text {out}}({\mathcal {L}}_{i-1, \ell ^\prime }{;} r, k^{\prime }) \} &{}{}\quad \text{ otherwise, } \end{array}\right. } \end{aligned}$$

where $\ell ^\prime \in \{i,\ell \}$ is an integer such that $\pi ^{-1}(\ell ^\prime ) \le \min \{\pi ^{-1}(i), \pi ^{-1}(\ell )\}$.

5.1.2 Running Time

Recall that a line representation ${\mathcal {L}}$ can be constructed in linear time from a given n-vertex permutation graph G. We add dummy line segments $L_0$ and $L_{n+1}$ and we then compute ${\mathcal {L}}_i$ and $\overline{{\mathcal {L}}_{i}}$ in O(n) time for every $i \in \{0, \ldots , n+1\}$. This preprocessing can be done in $O(n^2)$ time.

We bound the running time to compute $g_\textrm{max}({\mathcal {L}}_{i, \ell }{;} k^\prime )$, $g_{\textrm{in}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime )$, and $g_{\textrm{out}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime )$ for each integers $i, r, \ell$, and $k^\prime$, where $0 \le r\le i < \ell \le n+1$ and $0\le k^\prime \le k$. Notice that we do not need to consider an integer $r$ such that $|\overrightarrow{{\mathcal {L}}_{r}}| > k^\prime$ because it violates the condition that $|{\mathcal {S}}| = k^\prime$. Similarly, we can ignore an integer $\ell$ such that the size of $\{L_{i^\prime } \in \overline{{\mathcal {L}}_{i}} \mid \pi ^{-1}(i^\prime ) < \pi ^{-1}(\ell )\}$ is at least $k+1$. Thus, we can compute $g_\textrm{max}({\mathcal {L}}_{i, \ell }{;} k^\prime )$ in O(k) time for each triple $(i,\ell ,k^\prime )$, and compute $g_\textrm{max}({\mathcal {L}}_{i, \ell }{;} k^\prime )$ in $O(k^3n)$ time for all triples $(i,\ell ,k^\prime )$. Moreover, since both $g_{\textrm{in}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime )$ and $g_{\textrm{out}}({\mathcal {L}}_{i, \ell }{;} r, k^\prime )$ are computed in O(1) time for each quadruple $(i,r, \ell , k^\prime )$, they are computed in $O(k^3n)$ time for all quadruples $(i,r, \ell , k^\prime )$. Therefore, the total running time of our algorithm is $O(n^2 +k^3n)$, as claimed in Theorem 6. $\square$

5.2 d-Trapezoid Graphs

Our definition of d-trapezoid graphs follows [14]. Let d be a fixed positive integer and consider d horizontal parallel lines $L_1, L_2, \ldots , L_d$ on the plane. A polygon T is called d-trapezoid if an interval $[\textsf{left}_{j}(T), \textsf{right}_{j}(T)]$ on $L_j$ for each $j \in \{1,\ldots , d\}$ is defined and T is formed by connecting points $\textsf{left}_{1}(T), \textsf{left}_{2}(T), \ldots , \textsf{left}_{d}(T), \textsf{right}_{d}(T), \textsf{right}_{d-1}(T), \ldots , \textsf{right}_{1}(T), \textsf{left}_{1}(T)$. A graph $G = (V,E)$ with vertices $v_1, v_2, \ldots , v_n$ is called a d-trapezoid graph if there exists a set ${\mathcal {T}} = \{T_1, \ldots , T_n\}$ of d-trapezoids such that for any two distinct integers $i,j \in \{1,\ldots , n\}$, $v_iv_j \in E$ if and only if $T_i$ intersects with $T_j$. A set ${\mathcal {T}}$ of d-trapezoids that represents G is called a d-trapezoid diagram of G. Figure 9 shows an example of (a) a 3-trapezoid diagram and (b) its corresponding 3-trapezoid graph. Without loss of generality, for each $j \in \{1,\ldots , d\}$, we suppose that $\textsf{left}_{j}(T), \textsf{right}_{j}(T) \in \{1,\ldots , 2n\}$ for any $T \in {\mathcal {T}}$, and any intervals on $L_{j}$ have no endpoint in common.

Unfortunately, computing a d-trapezoid diagram of a given graph G is known to be NP-hard for any $d\ge 3$ [15]. We thus assume that a d-trapezoid diagram of G is also provided as part of an input of Maximum Happy Set.

Theorem 9

Given an n-vertex d-trapezoid graph G along with its d-trapezoid diagram and a non-negative integer k, Maximum Happy Set is solvable in $O(n^2 + d^2(k+1)^{3d}n)$ time.

Fig. 9

a The 3-trapezoid diagram ${\mathcal {T}}$. Each $T_i$ surrounded by a solid, dotted, or dashed rectangle is associated with a 3-trapezoid on ${\mathcal {T}}$ formed by the same type of lines. b The 3-trapezoid graph corresponding to ${\mathcal {T}}$

All interval graphs are 1-trapezoid graphs, and all permutation graphs and trapezoid graphs are 2-trapezoid graphs. Moreover, for $d \in \{1,2\}$, a d-trapezoid diagram of a given d-trapezoid graph can be obtained in polynomial time [10, 16]. Therefore, Theorem 9 indeed indicates the polynomial-time solvability of Maximum Happy Set on interval graphs, permutation graphs, and trapezoid graphs. Notice that Theorem 6 improves the running time of Theorem 9 for $d=2$ by applying good properties of permutation graphs.

Similar arguments for interval graphs in Sect. 4 are also applicable to d-trapezoid graphs. The only difference of our algorithm for d-trapezoid graphs is that vertices not contained in an optimal solution are characterized by a set of d-trapezoids of size at most 2d, whereas for interval graphs, such vertices are characterized by only two intervals. Thus, we here only describe the notations and the formulae to compute the optimal value without detailed proofs.

We first label d-trapezoids of ${\mathcal {T}}$ with $1, \ldots , n$ such that $\textsf{right}_{1}(T_i) < \textsf{right}_{1}(T_j)$ for any i, j with $1\le i < j \le n$. We add dummy trapezoids $T_0$ and $T_{n+1}$ into a d-trapezoid diagram of G, where $\textsf{right}_{j}(T_0) < \textsf{left}_{j}( T_1)$ and $\textsf{right}_{j}(T_n) < \textsf{left}_{j}(T_{n+1})$ for every $j \in \{1,\ldots , d\}$. Our task is to find an optimal solution ${\mathcal {S}}^*\subseteq {\mathcal {T}}{\setminus } \{T_0, T_{n+1}\}$ with the maximum set $H({\mathcal {T}}{;}\mathcal {S^*})$ of happy d-trapezoids. For an integer $i\in \{0,\ldots ,n+1\}$, we let ${\mathcal {T}}_i = \{T_0, T_1, \ldots , T_i\}$ and $\overline{{\mathcal {T}}_{i}} = {\mathcal {T}}{\setminus } {\mathcal {T}}_i$.

We next give the additional notations to define sets corresponding to $I_r$ and $I_\ell$ in Sect. 4. For non-empty sets ${\mathcal {R}}\subseteq {\mathcal {T}}_i$ and ${\mathcal {L}}\subseteq \overline{{\mathcal {T}}_{i}}$, let

• $\overrightarrow{{\mathcal {R}}} = \{ T \in {\mathcal {T}}_i \mid \forall T^\prime \in {\mathcal {R}}~ \exists j \in \{1,\ldots , d\}: \textsf{right}_{j}(T^\prime ) < \textsf{right}_{j}(T)\}$; and

• $\overleftarrow{{\mathcal {L}}} = \{ T \in \overline{{\mathcal {T}}_{i}} \mid \forall T^\prime \in {\mathcal {L}}~ \exists j \in \{1,\ldots , d\}: \textsf{left}_{j}(T) < \textsf{left}_{j}(T^\prime )\}$.

For two non-empty subsets ${\mathcal {R}}$ and ${\mathcal {R}}^\prime$ of ${\mathcal {T}}_i$, we say that ${\mathcal {R}}$ and ${\mathcal {R}}^\prime$ are equivalent, denoted by ${\mathcal {R}}\sim {\mathcal {R}}^\prime$, if $\overrightarrow{{\mathcal {R}}} = \overrightarrow{{\mathcal {R}}^\prime }$. Similarly, for two non-empty subsets ${\mathcal {L}}$ and ${\mathcal {L}}^\prime$ of $\overline{{\mathcal {T}}_{i}}$, we let ${\mathcal {L}}\sim {\mathcal {L}}^\prime$ if $\overleftarrow{{\mathcal {L}}} = \overleftarrow{{\mathcal {L}}^\prime }$. If ${\mathcal {R}}\subseteq {\mathcal {T}}_i$ is the inclusion-wise minimal set with respect to the equivalence class $[{\mathcal {R}}] = \{{\mathcal {R}}^\prime \mid {\mathcal {R}}\sim {\mathcal {R}}^\prime \}$, then ${\mathcal {R}}$ is called a representative of $[{\mathcal {R}}]$. Notice that such representative is uniquely determined. A representative of ${\mathcal {L}}\subseteq {\mathcal {T}}_i$ is also defined in the similar way. For sets ${\mathcal {R}}\subseteq {\mathcal {T}}_i$ and ${\mathcal {L}}\subseteq \overline{{\mathcal {T}}_{i}}$, the mappings $\textsf{rep}_{i}({\mathcal {R}})$ and $\textsf{rep}_{i}({\mathcal {L}})$ return the representatives of $[{\mathcal {R}}]$ and $[{\mathcal {L}}]$, respectively. For an optimal solution ${\mathcal {S}}^*\subseteq {\mathcal {T}}$, we let ${\mathcal {R}}^*= \textsf{rep}_{i}({\mathcal {T}}_i {\setminus } {\mathcal {S}}^*)$ and ${\mathcal {L}}^*= \textsf{rep}_{i}(\overline{{\mathcal {T}}_{i}} {\setminus } {\mathcal {S}}^*)$. Note that $\overrightarrow{{\mathcal {R}}}^*\subseteq {\mathcal {S}}^*$ and $\overleftarrow{{\mathcal {L}}}^*\subseteq {\mathcal {S}}^*$ hold. We guess non-empty sets ${\mathcal {R}}\subseteq {\mathcal {T}}_i$ and ${\mathcal {L}}\subseteq \overline{{\mathcal {T}}_{i}}$ such that ${\mathcal {R}}^*= {\mathcal {R}}$ and ${\mathcal {L}}^*= {\mathcal {L}}$, and then we compute a partial solution of ${\mathcal {T}}_i$ under the guess.

Let $\mathscr {R}_i$ and $\mathscr {L}_i$ be non-empty families of subsets of ${\mathcal {T}}_i$ and $\overline{{\mathcal {T}}_{i}}$ such that for each ${\mathcal {R}}\in \mathscr {R}_i$ and ${\mathcal {L}}\in \mathscr {L}_i$, ${\mathcal {R}}$ and ${\mathcal {L}}$ are the representatives of $[{\mathcal {R}}]$ and $[{\mathcal {L}}]$, respectively. We write ${\mathcal {T}}_{i,{\mathcal {L}}} = {\mathcal {T}}_i \cup {\mathcal {L}}$ and define the following function:

• $t({\mathcal {T}}_{i,{\mathcal {L}}}{;} {\mathcal {R}}, k^\prime )$ returns the maximum of $|H({\mathcal {T}}_{i,{\mathcal {L}}}{;}{\mathcal {S}})|$ among all subsets ${\mathcal {S}}\subseteq {\mathcal {T}}_{i,{\mathcal {L}}} {\setminus } (\{T_0\}\cup {\mathcal {R}}\cup {\mathcal {L}})$ such that $\overrightarrow{{\mathcal {R}}} \subseteq {\mathcal {S}}$ and $|{\mathcal {S}}| = k^\prime$.

We let $t({\mathcal {T}}_{i,{\mathcal {L}}}{;} {\mathcal {R}}, k^\prime ) = -\infty$ if there exists no subset ${\mathcal {S}}$ that satisfies all the prescribed conditions. Then, $t({\mathcal {T}}_{i,{\mathcal {L}}}{;} {\mathcal {R}}, k^\prime )$ is computed as follows: if $T_i \notin {\mathcal {R}}$,

$$\begin{aligned}&t({\mathcal {T}}_{i,{\mathcal {L}}}{;} {\mathcal {R}}, k^\prime ) \\&\quad = {\left\{ \begin{array}{ll} -\infty &{}\quad \text {if}\, i=0\, \text {or}\, k^\prime = 0, \\ t({\mathcal {T}}_{i-1,{\mathcal {L}}}{;} {\mathcal {R}}, k^{\prime }-1) &{}\quad \text {if}\, i>0, k^\prime > 0 \, \text {and}\, \exists T \in {\mathcal {R}}\cup {\mathcal {L}}: T_i \cap T \ne \emptyset , \\ t({\mathcal {T}}_{i-1,{\mathcal {L}}}{;} {\mathcal {R}}, k^{\prime }-1) +1&{}\quad \text {otherwise,} \end{array}\right. } \end{aligned}$$

and if $T_i \in {\mathcal {R}}$,

$$\begin{aligned}&t({\mathcal {T}}_{i,{\mathcal {L}}}{;} {\mathcal {R}}, k^\prime ) \\&\quad = {\left\{ \begin{array}{ll} 0 &{}\quad \text {if}\, i=0,{\mathcal {R}}= \{T_0\}, \, \text {and}\, k^\prime = 0, \\ \underset{\begin{array}{c} {\mathcal {R}}^\prime \in \mathscr {R}_{i-1} \\ \textsf{rep}_{i}({\mathcal {R}}^\prime \cup \{T_i\}) = {\mathcal {R}} \end{array}}{\max }t({\mathcal {T}}_{i-1,{\mathcal {L}}^\prime }{;} {\mathcal {R}}^\prime , k^{\prime }) &{}\quad \text {if}\, i>0, \\ -\infty &{}\quad \text {otherwise,} \end{array}\right. } \end{aligned}$$

where ${\mathcal {L}}^\prime = \textsf{rep}_{i-1}({\mathcal {L}}\cup \{T_i\})$.

5.2.1 Running Time

Obviously, the running time of our algorithm crucially depends on $\mathscr {R}_{i}$ and $\mathscr {L}_{i}$. The following lemma bounds the running time to construct $\mathscr {R}_{i}$ and $\mathscr {L}_{i}$, and their sizes.

Lemma 10

Suppose that, for each $j \in \{1, \ldots , d\}$, we have obtained a set of d-trapezoids in a d-trapezoid diagram ${\mathcal {T}}$ that are sorted in increasing order of the right endpoints of intervals on $L_{j}$. Then, for each $i \in \{0,\ldots , n\}$, $\mathscr {R}_{i}$ and $\mathscr {L}_{i}$ of each size at most $(k+1)^{d}$ can be constructed in $O(n + kd^2(k+1)^{2d})$ time.

Proof

For each $j \in \{1, \ldots , d\}$, let ${\mathcal {T}}_i^{j,k+1}$ be a maximal subset of ${\mathcal {T}}_i$ of size at most $k+1$ such that $\textsf{right}_{j}(T^\prime ) <\textsf{right}_{j}(T)$ for any $T \in {\mathcal {T}}_i^{j,k+1}$ and any $T^\prime \in {\mathcal {T}}_i {\setminus } {\mathcal {T}}_i^{j,k+1}$. In particular, if $i \le k+1$, we have ${\mathcal {T}}_i^{j,k+1} = {\mathcal {T}}_i$.

Recall that, for an optimal solution ${\mathcal {S}}^*$ of size k, we define ${\mathcal {R}}^*= \textsf{rep}_{i}({\mathcal {T}}_i {\setminus } {\mathcal {S}}^*)$ such that $\overrightarrow{{\mathcal {R}}}^*\subseteq {\mathcal {S}}^*$. Then, at least one d-trapezoid of ${\mathcal {R}}^*$ is contained in ${\mathcal {T}}_i^{j,k+1}$. Assume for a contradiction that there is no d-trapezoid of ${\mathcal {R}}^*$ in ${\mathcal {T}}_i^{j,k+1}$. This implies that ${\mathcal {T}}_i^{j,k+1} \subseteq \overrightarrow{{\mathcal {R}}}^*\subseteq {\mathcal {S}}^*$. If $i \le k+1$, then ${\mathcal {T}}_i = {\mathcal {T}}_i^{j,k+1} \subseteq {\mathcal {S}}^*$, which contradicts that $T_0 \notin {\mathcal {S}}^*$ and hence ${\mathcal {T}}_i {\setminus } {\mathcal {S}}^*\ne \emptyset$. If $i \ge k+1$, then the size of ${\mathcal {T}}_i^{j,k+1}$ is exactly $k+1$, which contradicts that the size of ${\mathcal {S}}^*$ is exactly k.

In addition, for each $T \in {\mathcal {R}}^*$, there exists $j \in \{1, \ldots , d\}$ such that $\textsf{right}_{j}(T^\prime ) <\textsf{right}_{j}(T)$ for any $T^\prime \in {\mathcal {R}}^*{\setminus } \{T\}$; otherwise, ${\mathcal {R}}^*$ is not minimal with respect to the equivalence class $[{\mathcal {R}}^*]$, contradicting that ${\mathcal {R}}^*= \textsf{rep}_{i}({\mathcal {T}}_i {\setminus } {\mathcal {S}}^*)$. Therefore, we construct $\mathscr {R}_{i}$ as follows. We enumerate possible candidates of ${\mathcal {R}}^*$ by picking a d-trapezoid in ${\mathcal {T}}_i^{j,k+1}$ for each $j \in \{1,\ldots , d\}$ repeatedly. Let $\mathscr {R}_{i}^\prime$ be a family of the enumerated sets. Then, we remove ${\mathcal {R}}\in \mathscr {R}_{i}^\prime$ from $\mathscr {R}_{i}^\prime$ if it is inappropriate as a candidate because $|\overrightarrow{{\mathcal {R}}}| > k$, or it is redundant, that is, there exists ${\mathcal {R}}^\prime \in \mathscr {R}_{i}^\prime$ such that ${\mathcal {R}}\sim {\mathcal {R}}^\prime$ and $|{\mathcal {R}}| \ge |{\mathcal {R}}^\prime |$. Let $\mathscr {R}_{i}$ be a family obtained after the reduction.

We bound the running time to construct $\mathscr {R}_{i}$. Recall that, for each $j \in \{1, \ldots , d\}$, we have sorted d-trapezoids in a d-trapezoid diagram ${\mathcal {T}}$ in increasing order of the right endpoints of intervals on $L_{j}$. For each $i \in \{0,\ldots , n\}$, we can obtain ${\mathcal {T}}_i^{j,k+1}$ in O(n) time. Then, we construct $\mathscr {R}_{i}^\prime$. Since the size of ${\mathcal {T}}_i^{j,k+1}$ is at most $k+1$ for every $j \in \{1,\ldots , d\}$, the size of $\mathscr {R}_{i}^\prime$ is at most $(k+1)^d$. To obtain $\mathscr {R}_{i}$ from $\mathscr {R}_{i}^\prime$, we remove inappropriate sets as candidates of ${\mathcal {R}}^*$ from $\mathscr {R}_{i}^\prime$. Notice that for each ${\mathcal {R}}\in \mathscr {R}_{i}^\prime$, we can construct $\overrightarrow{{\mathcal {R}}}$ in $O(kd^2)$ time because $|{\mathcal {R}}| \le d$ and ${\mathcal {T}}_i^{j,k+1}$ has the size at most $k+1$ for each $j \in \{1, \ldots , d\}$. After removing all sets ${\mathcal {R}}\in \mathscr {R}_{i}^\prime$ with $|\overrightarrow{{\mathcal {R}}}| > k$ from $\mathscr {R}_{i}^\prime$, we also remove redundant sets by checking whether ${\mathcal {R}}\sim {\mathcal {R}}^\prime$ and $|{\mathcal {R}}| \ge |{\mathcal {R}}^\prime |$ for each pair ${\mathcal {R}}, {\mathcal {R}}^\prime \in \mathscr {R}_{i}^\prime$. This reduction of $\mathscr {R}_{i}^\prime$ can be done in $O(kd^2\cdot |\mathscr {R}_{i}^\prime | + (k+d)\cdot |\mathscr {R}_{i}^\prime |^2) = O(kd^2(k+1)^{2d})$ time. Consequently, $\mathscr {R}_{i}$ of size at most $(k+1)^d$ is obtained in $O(n + kd^2(k+1)^{2d})$ time for each $i \in \{0,\ldots , n\}$. The similar construction of $\mathscr {L}_{i}$ can also be done in $O(n + kd^2(k+1)^{2d})$ time for each $i \in \{0,\ldots , n\}$. $\square$

We now estimate the running time of our algorithm. First, for each $j \in \{1,\ldots , d\}$, we sort d-trapezoids in a d-trapezoid diagram ${\mathcal {T}}$ in O(n) time in increasing order of the right endpoints of intervals on $L_{j}$ and store the results of sorting. We then compute ${\mathcal {T}}_i$, $\overline{{\mathcal {T}}_{i}}$, $\mathscr {R}_{i}$, and $\mathscr {L}_{i}$ for each $i \in \{0,\ldots , n\}$. From Lemma 10, this can be done in $O(n^2 + kd^2(k+1)^{2d}n)$ time.

Consider a quadruple $(i, {\mathcal {R}}, {\mathcal {L}}, k^\prime )$, where ${\mathcal {R}}\in \mathscr {R}_{i}$, ${\mathcal {L}}\in \mathscr {L}_{i}$, and $k^\prime \in \{0,\ldots , k\}$. If $T_i \notin {\mathcal {R}}$, we check whether $\exists T \in {\mathcal {R}}\cup {\mathcal {L}}: T_i \cap T \ne \emptyset$, where $|{\mathcal {R}}\cup {\mathcal {L}}| \le 2d$ because $|{\mathcal {R}}| \le d$ and $|{\mathcal {L}}| \le d$. For a trapezoid $T \in {\mathcal {R}}\cup {\mathcal {L}}$, the following observation allows us to check whether $T_i \cap T \ne \emptyset$ in O(d) time.

Observation 11

Let ${\mathcal {T}}$ be a d-trapezoid diagram. For two trapezoids $T, T^\prime \in {\mathcal {T}}$, $T \cap T^\prime = \emptyset$ if and only if

• (1) $\textsf{right}_{j}(T) < \textsf{left}_{j}(T^\prime )$ for every $j \in \{1,\ldots , d\}$, or

• (2) $\textsf{right}_{j}(T^\prime ) < \textsf{left}_{j}(T)$ for every $j \in \{1,\ldots , d\}$.

Thus, if $T_i \notin {\mathcal {R}}$, the value $t({\mathcal {T}}_{i,{\mathcal {L}}}{;} {\mathcal {R}}, k^\prime )$ is computed in $O(d^2)$ time.

If $T_i \in {\mathcal {R}}$, we first obtain $\textsf{rep}_{i-1}({\mathcal {L}}\cup \{T_i\})$ in $O(d^2)$ time by removing a d-trapezoid T from ${\mathcal {L}}\cup \{T_i\}$ such that $\textsf{left}_{j}(T_i) < \textsf{left}_{j}(T)$ for every $j \in \{1,\ldots , d\}$. Then, for each ${\mathcal {R}}^\prime \in \mathscr {R}_{i-1}$, we check in $O(d^2)$ time whether $\textsf{rep}_{i}({\mathcal {R}}^\prime \cup \{T_i\}) = {\mathcal {R}}$ and obtain a value $t({\mathcal {T}}_{i-1,{\mathcal {L}}^\prime }{;} {\mathcal {R}}^\prime , k^{\prime })$ in O(1) time. Thus, if $T_i \in {\mathcal {R}}$, the value $t({\mathcal {T}}_{i,{\mathcal {L}}}{;} {\mathcal {R}}, k^\prime )$ is computed in $O(d^2 + d^2\cdot |\mathscr {R}_{i-1}|) = O(d^2(k+1)^{d})$ time.

We finally bound the total running time of our algorithm. The preprocessing can be done in $O(n^2 + kd^2(k+1)^{2d}n)$ time. Since $|\mathscr {R}_{i}| \le (k+1)^d$ and $|\mathscr {L}_{i}| \le (k+1)^d$, if $T_i \notin {\mathcal {R}}$, our algorithm computes the value $t({\mathcal {T}}_{i,{\mathcal {L}}}{;} {\mathcal {R}}, k^\prime )$ in $O(d^2(k+1)^{2d+1}n)$ time for all quadruples $(i, {\mathcal {R}}, {\mathcal {L}}, k^\prime )$. Notice that the number of ${\mathcal {R}}\in \mathscr {R}_i$ such that $T_i \in {\mathcal {R}}$ is at most $(k+1)^{d-1}$. Therefore, for all quadruples $(i, {\mathcal {R}}, {\mathcal {L}}, k^\prime )$ with $T_i \in {\mathcal {R}}$, our algorithm computes the value $t({\mathcal {T}}_{i,{\mathcal {L}}}{;} {\mathcal {R}}, k^\prime )$ in $O(d^2(k+1)^{d}\cdot (k+1)^{2d} n) = O(d^2(k+1)^{3d}n)$ time. As a conclusion, we obtain an optimal solution of Maximum Happy Set on a d-trapezoid graph in $O(n^2 + d^2(k+1)^{3d}n)$ time. This completes the proof of Theorem 9. $\square$

6 Conclusion

In this paper, we studied the complexity of Maximum Happy Set on subclasses of co-comparability graphs; co-bipartite graphs, interval graphs, permutation graphs, and d-trapezoid graphs. Especially, our algorithm for interval graphs improved the best known running time $O(kn^8)$. Our polynomial-time algorithms employ basically the same techniques.

The complexity of Maximum Happy Set has been studied for various graph classes. However, the (in)tractability of Maximum Happy Set on planar graphs remains open. We note that the complexity of the edge variant [9] of Maximum Happy Set is also unknown for planar graphs.