Recognition of chordal graphs and cographs which are Cover-Incomparability graphs

The cover-incomparability graphs of posets, or shortly C-I graphs form an interesting class of graphs from posets. These graphs were introduced in [8] as the underlying graphs of the so-called standard transit function of posets. The C-I graphs are precisely the graphs whose edge set is the union of edge sets of the cover graph and the incomparability graph (complement of a comparability graph) of a poset. Graph-theoretic characterization of C-I graphs has not been known until now and, moreover, the recognition complexity of C-I graphs is NP-complete (Maxová et al. [24]). Hence, problems in C-I graphs are focused on identifying the structure and characterization of well-known graph families, which are C-I graphs. Such C-I graphs studied include the family of split graphs, block graphs [7], cographs [9], Ptolemaic graphs [25], distance-hereditary graphs [25], and $k$-trees [23]. The C-I graphs were identified among the planar and chordal graphs along with new characterizations of the Ptolemaic graphs, respectively, in [4] and [3]. It is also interesting to note that every C-I graph has a Ptolemaic C-I graph as a spanning subgraph [4]. C-I graphs are also studied among the comparability graphs [1]. The effect of composition operation, lexicographic, and strong products of C-I graphs was studied in a recent paper [2].

Another approach in the theory of C-I graphs is to study posets whose cover-incomparability graphs exhibit specific properties [7, 8, 9]. Characterizations of posets whose cover-incomparability graphs are distance-hereditary and Ptolemaic were given in [8], while those for cographs appear in [9], and for block graphs and split graphs in [7], in terms of forbidden isometric subposets. However, the characterization in terms of forbidden ‘isometric subposets’ in [7, 8, 9] was an error, and it was resolved in [6] by introducing $\lhd$-preserving subposets instead of isometric subposets.

Chordal graphs or triangulated graphs are graphs that do not have induced cycles of length greater than three. Together with cographs, which are exactly $P_{4}$-free graphs, they form two well-studied graph classes that have wider applications beyond mathematics. These two classes of graphs and their subclasses are also studied in many contexts, including theoretical, practical, and algorithmic interests. A vertex $v$ of a graph $G$ is a simplicial vertex if $v$ together with all its adjacent vertices forms a clique (a complete subgraph) in $G$. It is a well-known fact that every chordal graph contains at least one simplicial vertex, and a non complete chordal graph contains at least two nonadjacent simplicial vertices. Chordal graphs that contain exactly two non-adjacent simplicial vertices form a special class of chordal graphs.

The recognition algorithm for an arbitrary chordal graph [30, 27] and a cograph [14] is well known and has linear-time complexity. In this paper, we identify chordal graphs having exactly two non-adjacent simplicial vertices and prove that they are C-I graphs. In other words, we prove that the intersection of the class of chordal graphs and the class of C-I graphs is precisely the class of chordal graphs having exactly two non-adjacent simplicial vertices. We further develop a linear-time algorithm for recognizing such chordal graphs. It is interesting to observe, from [4, 7], that in the class of C-I graphs, the classes of chordal, strongly chordal, and interval graphs are one and the same.

In this paper, similar to the chordal C-I graphs, we develop a linear-time recognition algorithm for cographs which are also C-I graphs from the structural results already proved in [9]. For this algorithm, we make use of the special type of cotree structure of cographs.

Chordal graphs are precisely the intersection graphs of subtrees of a tree [20]. Most of the information contained in a chordal graph is captured in its clique tree representation, which is useful for its algorithmic applications [20, 29].

Cographs are exactly the $P_{4}$-free graphs and the class of cographs has been intensively studied since its definition by Seinsche [28]. The cographs appear as comparability graphs of series-parallel partial orders [22], and can be generated from the single-vertex graph $K_{1}$ by complementation and disjoint union operations. It is well known that any cograph has a canonical tree representation called a cotree. This tree decomposition scheme for cographs is a particular case of modular decomposition [19] that applies to arbitrary graphs. Indeed, the algorithm that computes the modular tree decomposition of an arbitrary graph in linear-time can also recognize cographs in linear-time. In 1994, linear-time modular decomposition algorithms were designed independently by Cournier and Habib [15] and by McConnell and Spinrad [26]. In 2001, Dahlhaus et al. [16] proposed a simpler algorithm. In 2004, Habib and Paul [21] proposed a new algorithm, which is not incremental, and instead of building the cotree directly, it first computes a special ordering of the vertices, namely a factorizing permutation, using a very efficient partition refinement techniques via two elementary refinement rules.

A search of a graph visits all vertices and edges of the graph and will visit a new vertex only if it is adjacent to some previously visited vertex. The two fundamental search strategies are Breadth-First Search (BFS) and Depth-First Search (DFS). As the names indicate, BFS visits all previously unvisited neighbors of the currently visited vertex before visiting the previously unvisited non-neighbors. Several greedy recognition algorithms for chordal graphs are known. The most famous is Lex-BFS [27], a variant of $BFS$, introduced by Rose et al. in [27] and Maximum Cardinality Search (MCS for short) [30]. Both algorithms are linear. The recognition of chordal graphs involves two distinct phases: the execution of MCS or Lex-BFS in order to compute an elimination ordering and a checking procedure to decide whether this elimination ordering is perfect (PEO). By employing Lex-BFS as a basic method to check the chordality and to find the perfect elimination ordering, the recognition algorithm for the chordal graphs can be done in linear-time for chordal graphs which are C-I graphs. For cographs, using the BFS, we can check whether a given rooted tree is the cotree of the C-I cograph in linear-time because of the special structure of the cotrees of these graphs.

The rest of this section is organized as follows. In Section  2, we begin with some preliminaries. In Section 3, we characterize chordal C-I graphs in terms of the number of independent simplicial vertices and present a linear-time algorithm for recognizing chordal C-I graphs based on this characterization. In Section 4, we present a structure of the C-I cograph and characterize the structure of the cotree of C-I cographs and, using this, present a linear-time recognition algorithm for C-I cographs.

A partially ordered set or poset $P=(V,\leq)$ consists of a nonempty set $V$ and a reflexive, antisymmetric, transitive relation $\leq$ on $V$, denoted as $P=(V,\leq)$. We call $u\in V$ an element of $P$. If $u\leq v$ or $v\leq u$ in $P$, we say $u$ and $v$ are comparable, otherwise incomparable. If $u\leq v$ but $u\neq v$, then we write $u<v$. If $u$ and $v$ are in $V$, then $v$ covers $u$ in $P$ if $u<v$ and there is no $w$ in $V$ with $u<w<v$, denoted by $u\lhd v$. We write $u\lhd\lhd v$ if $u<v$ but not $u\lhd v$. By $u||v$, we mean that $u$ and $v$ are incomparable elements of $P$. In this paper, we consider only posets defined on finite sets. Let $V^{\prime}\subseteq V$ and $Q=(V^{\prime},\leq^{\prime})$ be a poset, $Q$ is called a subposet of $P$, if $u\leq^{\prime}v$ if and only if $u\leq v$, for any $u,v\in V^{\prime}$. The subposet $Q=(V^{\prime},\leq)$ is a chain (antichain) in $P$, if every pair of elements of $V^{\prime}$ is comparable (incomparable) in $P$. A chain of maximum cardinality is named as the height of $P$ denoted as $h(P)$. An element $u$ in $P$ is a minimal (maximal) if there is no $x\in V$ such that $x\leq u(u\leq x)$ in $P$. A finite ranked poset (also known as graded poset [11]) is a poset $P=(V,\leq)$ that is equipped with a rank function $\rho:V\rightarrow\mathbb{Z}$ satisfying:

• •

  $\rho$ has value $0$ on all minimal elements of $P$, and

• •

  $\rho$ preserves covering relations: if $a\lhd b$ then $\rho(b)=\rho(a)+1$.

A ranked poset $P$ is said to be complete if for every $i$, every element of rank $i$ covers all elements of rank $i-1$. For a completely ranked poset $P=(V,\leq)$ we say that the element $v\in V$ is at height $i$ if $\rho(v)=i-1$. For disjoint posets, $P_{1}=(V_{1},\leq)$ and $P_{2}=(V_{2},\leq)$, the sum of the posets, $Z=P_{1}+P_{2}$ is defined as the poset $(V_{1}\cup V_{2},\leq)$, where $z_{1}\in z_{2}$ in $Z$, if and only if $z_{1}\leq z_{2}$ in $P_{1}$ or $z_{1}\leq z_{2}$ in $P_{2}$. We refer to [11], for notions of posets.

Let $G=(V,E)$ be a connected graph, vertex set and edge set of $G$ denoted as $V(G)$ and $E(G)$ respectively, the complement of $G$ is denoted as $\overline{G}$. For a vertex $v\in V(G)$, the set of all vertices adjacent to $v$ is called the open neighborhood of $v$ and is denoted by $N(v)$. The set consisting of the open neighborhood and the vertex $v$ is the closed neighborhood of $v$ and is denoted by $N[v]$. A tree is a graph in which two vertices are connected by exactly one path. Let $T$ be a rooted tree and two vertices $x$ and $y$ in $T$, we say that $x$ is an ancestor of $y$ and $y$ is a descendant of $x$ if $x$ lies on the path from $y$ to the root of $T$. For a set of leaves $S$ of $T$, we say that the lowest common ancestor (LCA) of $S$ is the internal node $v$ of $T$ such that $v$ is the root of the smallest rooted subtree of $T$ containing $S$. A graph $H$ is said to be a subgraph of $G$ if $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G)$. $H$ is an induced subgraph of $G$ if for $u,v\in V(H)$ and $uv\in E(G)$ implies $uv\in E(H)$. A graph $G$ is said to be H-free if $G$ has no induced subgraph isomorphic to $H$. A complete graph is a graph whose vertices are pairwise adjacent, denoted $K_{n}$, a set $S\subseteq V(G)$ is a clique if the subgraph of $G$ induced by $S$ is a complete graph, and a maximum clique is a clique that is not contained by any other clique. A vertex $v$ is called simplicial vertex if its neighborhood induces a complete subgraph. An independent set in a graph is a set of pairwise non-adjacent vertices. If graphs $G_{1}$ and $G_{2}$ have disjoint vertex set $V_{1}$ and $V_{2}$ and edge set $E_{1}$ and $E_{2}$ respectively, then their union $G=G_{1}\cup G_{2}$ has $V=V_{1}\cup V_{2}$ and $E=E_{1}\cup E_{2}$ and their join, denoted by $G_{1}\vee G_{2}$, consists of $G=G_{1}\cup G_{2}$ and all edges joining $V_{1}$ with $V_{2}$.

A graph $G$ is chordal if it contains no induced cycles of length more than 3. A graph $G$ is distance-hereditary if every induced path is also the shortest path in $G$. A graph $G$ is Ptolemaic if it is distance-hereditary and chordal. Equivalently, $G$ is Ptolemaic if and only if it is a 3-fan-free chordal graph. $P_{4}$-free graphs are called cographs. A graph $G$ that is both chordal and cograph is called chordal cograph, also known as trivially perfect graph. Let $P=(V,\leq)$ be a poset. A graph $G$ is the cover graph of $P$ if $V(G)=V$ and $uv\in E(G)$ if and only if either $u\lhd v$ or $v\lhd u$ in $P$. Similarly, $G$ is the comparability graph of $P$ if $V(G)=V$ and $uv\in E(G)$ if and only if $u$ and $v$ are comparable in $P$. The incomparability graph is the complement of the comparability graph. Finally, the cover-incomparability graph (C-I graph) of a poset $P=(V,\leq)$ denoted as $G_{P}$ is the graph $G=(V,E)$, where $uv\in E(G)$, if $u\lhd v$ or $v\lhd u$ or $u||v$ in $P$. A graph is a C-I graph if it is the C-I graph of some poset $P$. It may be noted that the class of C-I graphs is not a hereditary class in the sense that every induced subgraph of a C-I graph need not be a C-I graph. We call a graph that is both a chordal and a C-I graph as a chordal C-I graph. Similarly, we use the term Ptolemaic C-I graph, C-I cograph, chordal C-I cograph, etc. to denote the C-I graph which is Ptolemaic, cograph, chordal cograph, etc.

In Figure 1 (a), we illustrates the Hasse diagram of a poset $P$, which is isomorphic to the cover graph of $P$. Figure 1(b), depicts the incomparability graph of the poset $P$, and in Figure 1(c), we depicts the C-I graph of $P$. As already mentioned, the class of C-I graphs is not hereditary; for example, the 4-fan is a C-I graph (as shown in Figure 1(c)), but the claw graph is an induced subgraph of this graph, which is not a C-I graph.

Now we recall some basic properties of posets and their C-I graphs.

In the following sections, we discuss algorithms for recognizing chordal C-I graphs and C-I cographs.

In this section, we study the structure of chordal C-I graphs. For that, we prove that a chordal graph having exactly two independent vertices is a chordal graph that is also a C-I graph.

If $v$ is a simplicial vertex of a chordal graph $G$, then the closed neighborhood $N[v]$ is a clique in $G$. So removal of $v$ does not affect the chordal property of $G\setminus\{v\}$. This is stated in the following remark.

From Lemmas 3-4 and Theorem 1, we get the following corollary.

A pendant clique of a graph $G$ is a clique that contains a clique separator $C$ such that one of the components obtained after removing $C$ is a single vertex. Observe that if $G$ is a chordal graph, then $G$ has a pendant clique.

Let $G$ be a chordal graph having at most two independent simplicial vertices. We denote by $\mathscr{G}$ the family of chordal graphs obtained from $G$ by adding a vertex $v$ to $G$ such that $v$ is adjacent to some or all vertices in a pendant clique of $G$.

The following remark is immediate.

A perfect elimination ordering (PEO) is an ordering $\pi=v_{1},\ldots,v_{n}$ of vertices in $G$ such that the neighborhood $N[v_{i}]$ of $v_{i}$ is a clique of the subgraph $G_{\{v_{i},\ldots,v_{n}\}}$ induced by the vertices $\{v_{i},\ldots,v_{n}\}$ of $G$. The following characterizations of chordal graphs are well known.

In the following, we prove an interesting characterization of C-I chordal graphs as precisely those chordal graphs having exactly two independent simplicial vertices.

In this section, we present an algorithm for recognizing C-I cograph.

From Theorem 5, we get the following remark

That is, $C_{1},C_{2},C_{3},C_{1}\cup C_{2}$ and $C_{2}\cup C_{3}$ form cliques and the graph has no other edges. So in the C-I chordal cograph, if $xy,xz\notin E(G)$ then $yz\in E(G)$. It is clear that a chordal C-I cograph is a Ptolemaic C-I graph as it is a C-I graph of a completely ranked poset of height 3. The structure of an arbitrary chordal C-I cograph is shown in Fig. 3.

From Theorem 6, we get the following remark.

The structure of an arbitrary C-I cograph is depicted in Fig. 4.

A cotree is a tree in which the internal nodes are labelled with the numbers 0 and 1. Every cotree $T$ defines a cograph $G$ having the leaves of $T$ as vertices, and in which the subtree rooted at each node of $T$ corresponds to the induced subgraph in $G$ defined by the set of leaves descending from that node. A subtree rooted at a node labelled 0 corresponds to the union of the subgraphs defined by the children of that node and a node labelled 1 corresponds to the join of the subgraphs defined by the children of that node. The cotree satisfies the property that, on every root-to-leaf path, leaves are the vertices of the graph, the labels of the internal nodes alternate between 0 and 1, and every internal node has at least two children. The cotree can be easily obtained from any tree labelled with such $0/1$ $T$ by coalescing all pairs of child-parent nodes in $T$ having the same label or where the parent has only one child. Vertices $x$ and $y$ of $G$ are adjacent in $G$ if and only if their lowest common ancestor(LCA) in the cotree is labelled 1. This representation is unique and every cograph can be represented in this way by a cotree [13]. Since $G$ is a connected graph, the root of the cotree is a 1-node.

It is known that cographs have a unique tree representation, called a cotree. Using the cotree, it is possible to design very fast polynomial-time algorithms for problems that are intractable for graphs in general. Such problems include chromatic number, clique determination, clustering, minimum weight domination, isomorphism, minimum fill-in, and Hamiltonicity. A linear-time cograph recognition algorithm, such as those in [10, 14, 21], which also builds a cotree, a data structure that fully encodes the cograph.

The Fig. 6 illustrates a cograph $G$ and an embedding of the corresponding cotree $T_{G}$. The leaves of $T_{G}$ represent the set of vertex $V(G)$, and each internal node signifies the union (0) or the joining (1) operations in the children. The significance of the 0(1) nodes is captured by the fact that $xy\in E(G)$ if and only if $LCA(x,y)$ is a 1 node, as shown in Fig. 6.

The general structure of the cotree of C-I cographs is shown in Fig. 7, and we denote the family of cotree of C-I cograph as $\mathcal{T_{C}}$. The children of the root node are referred to as level 2 nodes, while the children of level 2 nodes are termed level 3 nodes. Let $G$ be a C-I cograph, $G=G_{1}\vee G_{2}\vee\cdots\vee G_{k}$, where $G_{i}$’s are chordal C-I cographs. Then by Remark 4, two vertices $x$ and $y$ are not adjacent in $G$ if and only if $x\in C_{1}^{i}$ and $y\in C_{3}^{i}$ for $i=1,2,\ldots,k$. Therefore, in the cotree, the lowest common ancestor(LCA) of $x$ and $y$ is 0-node. That is, $LCA(x,y)=0$ for $x\in C_{1}^{i}$ and $y\in C_{3}^{i}$. In other cases, LCA is a 1-node. That is, $LCA(x,y)=0$ for $x\notin C_{1}^{i}$ and $y\notin C_{3}^{i}$.

In [14], Corneil et al. presented a linear-time algorithm for recognizing cographs and constructing their cotree representation. Using that algorithm, we get the cotree.

Proof of correctness: The correctness of the Algorithm 2 up to step 5 follows from the structure of cotree stated in Lemma 12 and Theorem 7, and the related facts mentioned above. If after step 5 results in a C-I cograph, then the poset $P=P_{1}+P_{2}+\cdots+P_{r}$ is certification and it follows from Remark 4, Lemma 10 and Theorem 7 that it is one of the completely ranked poset corresponding to the input graph $G$.

Now the size of the cotree of a C-I cograph can be estimated as follows. Let $G$ be a C-I cograph with $n$ vertices and $G=G_{1}\vee G_{2}\vee\cdots G_{k}$. Then from the structure of the cotree $T$ of $G$, $T$ contains leaf nodes (which are the $n$-vertices of $G$), 0-nodes, and 1-nodes. Then $T$ contains $k$ 0-nodes, and each 0-node has exactly 2 children. Therefore $T$ has at most $1+k+2k+n$ vertices. The worst case for $k$ is when $k=\frac{n}{3}$. Therefore in the worst case, the total number of vertices in $T$ is $1+\frac{n}{3}+\frac{2n}{3}+3$, which is of the order of $O(n)$.

The time complexity of the recognition algorithm for cographs and finding its cotree by Theorem 8 is linear. Now the complexity of Algorithm 2 is linear in the size of the cotree, which is $O(n)$ in the worst case since the complexity of the BFS can be performed on the cotree in linear-time.