Efficient Algorithm for Checking 2-Chordal (Doubly Chordal) Bipartite Graphs

The study of chordal graphs can be traced back to 1958 when they were first introduced by Hajnal and Surányi. These are the graphs for which every cycle of length four or greater contains a chord [1]. Since then several subclasses and variations of chordal graphs, notably bipartite analogs, have been introduced. Of interest to us is the notion of a 2-chordal bipartite (also known as a doubly chordal bipartite) graph which was recently connected to discrete statistical models and their maximum likelyhood degrees [2]. Efficient algorithm for recognizing chordal graphs and chordal bipartite graphs are known and are of polynomial complexity on the size of the vertex set[3] [4] [5]. 2-chordal bipartite graphs can be characterized as those bipartite graphs which are chordal bipartite and lack a double-square graphs as an induced subgraph, however the induced subgraph problem is known to be NP-complete in general [2] [6].

In this work, we present an efficient algorithm for checking whether a graph is 2-chordal bipartite and as a corollary show that the induced subgraph problem for the double-square graph is solvable in polynomial time. The algorithm breaks into two components- the first being the check that the graph is chordal bipartite and the second being an iterative process which runs over all edge deletions and is based on the vertex characterization due to Farber. We also show that the conditions checked are both necessary and sufficient conditions (although there may be a faster check for them) and then characterize the runtime of the algorithm. The key theorem underlying this algorithm is Theorem 3.1.

We also introduce and explore the natural generalization of Theorem 3.1 to $k$-chordal bipartite graphs. This generalization allows us to propose algorithms which check the property of being $k$-chordal bipartite and we show that they are also in complexity class $P$ for all $k$. However, we provide a proof that there are no nontrivial $k$-chordal bipartite graphs for $k\geq 4$ where nontrivial means that they contain a cycle of size at least $6$ and in doing so remove the need for anything other than the $k=2,3$ algorithms.

In this section we lay out a few foundational results about chordal and strongly chordal graphs as well as their connection to chordal bipartite graphs. Formally, a chordal graph is a simple graph possessing no chordless cycles of length four or greater. Such a cycle is called a hole and so a chordal graph is a graph without holes [1]. A subclass of these graphs, introduced by Farber, is the strongly chordal graphs; these are chordal graphs for which every even cycle of length at least 6 has a strong chord, i.e. a chord joining vertices whose distance along the cycle is odd [3]. As we will see, strongly chordal graphs are closely related to another subclass found among bipartite graphs.

We will put a name to two special types of vertices: simplicial vertices and simple vertices. A simplicial vertex is a vertex whose open neighborhood forms a clique; that is, a vertex $v$ in the graph $G$ is simplicial if the subgraph induced on $N_{G}(v)$ is a complete graph. Meanwhile, a simple vertex is a vertex whose neighbors have closed neighborhoods which can be ordered as a chain under inclusion; that is, a vertex $v$ in the graph $G$ with open neighborhood $N_{G}(v)=\{v_{1},...,v_{k}\}$ is simple if there exists some relabeling $\sigma$ on $[k]$ such that

Observe that every simple vertex is also simplicial. The proof is as follows, suppose $v$ is a simple vertex and consider the induced subgraph on $N_{G}(v)$. It suffices to show that for any pair of edges $u,w\in N_{G}(v)$ there is an edge between them. As the set of closed neighbhorhoods of neighbors of $v$ form a chain, we have either $u\in N_{G}[u]\subseteq N_{G}[w]$ or $w\in N_{G}[w]\subseteq N_{G}[u]$. In either case, $uw\in E(G)$ as desired.

These distinguished vertex classes play an important role in the theory of chordal graphs. A graph is chordal if and only if every induced subgraph contains a simplicial vertex and a graph is strongly chordal if and only if every induced subgraph has a simple vertex [3] [4]. These properties lend themselves to finding chordal and strongly chordal graphs by means of algorithms which perform a simplicial elimination ordering or a simple elimination ordering respectively; that is, an algorithm to determine whether a graph is chordal (strongly chordal) is to search the graph for a simplicial (simple) vertex, form the subgraph induced by removing it, and repeat. Such an algorithm effectively checks either that there are sufficiently many simplicial vertices- i.e. every induced subgraph contains at least one of them- or it identifies a particular induced subgraph which does not contain a simplicial vertex. Note that the algorithm does not run over all induced subgraphs nor is it a requirement to do so.

These algorithms provide polynomial-time methods of determining characteristics of graphs. For strong chordal graphs, the simple elimination ordering is equivalent to the strong elimination ordering which is an ordering $v_{1},...,v_{n}$ of the vertices such that if (i) $i<j$ and $k<l$, (ii) $v_{k},v_{l}\in N[v_{i}]$, (iii) $v_{j}\in N[v_{k}]$, then $v_{l}\in N[v_{j}]$ [5]. There are numerous other characterizations of strongly chordal graphs which include sun-characterizations, hereditary dually chordal characterizations, hypertree characterizations, and $(n+4)$-vertex cycle subgraph characterizations [7]. One characterization that we will briefly touch on is the hypergraph characterization. A graph is chordal if and only if the hypergraph of its maximal cliques is the dual of a hypertree. This leads us to the definition of a dually chordal graph, which is a graph whose hypergraph of maximal cliques is itself a hyperrtree. A graph is called doubly chordal if it is both chordal and dually chordal. This naming convention will influence our choice of nomenclature when it comes to bipartite graphs.

We now turn our attention to bipartite graphs proper and their subclasses. A bipartite graph is chordal bipartite if every cycle of length greater than or equal to 6 has a chord. A bipartite graph is 2-chordal bipartite if every cycle of length greater than or equal to 6 has at least two chords. This property has also been called “doubly chordal bipartite” in the literature, but due to the classical definition of doubly chordal mentioned above we have adopted “2-chordal bipartite” in its place [2]. If $G=(X,Y,E)$ is a bipartite graph and $G^{\prime}$ is the graph obtained from $G$ by adding an edge in-between every pair of vertices in $X$, then $G$ is chordal bipartite if $G^{\prime}$ is strongly chordal [7]. This provides a link between our concepts. An important observation is that a chordal bipartite graph need not be chordal. For example, consider the graph $C_{4}$ with $V(C_{4}):=\{a,b,c,d\}$ and $E(C_{4}):=\{\{a,b\},\{c,d\},\{ac,ad,bc,bd\}\}$. Clearly this graph is vacuously chordal bipartite as it contains no cycles of length 6. However, it contains the cycle $acbd=ac+cb+bd+ac$, of length 4, and this cycle contains no chords (in fact, it uses every edge of $C_{4}$ as highlighted by the addition).

We begin with our main algorithm which takes a bipartite graph as input and answers the yes/no question of whether or not the graph is 2-chordal bipartite. We define two classes beforehand. The first is the class graph which is initialized with a triple containing its name, vertex set, and edge set given as pairs of vertices. For its methods it has the usual graph operations as well as a method called simple which takes as input a vertex and outputs a boolean value representing whether or not the vertex is simple. The second class is biGraph which is initialized with a 4-tuple containing its name, two disjoint vertex sets, and its edge set given as pairs selected from both sets. Its methods are the usual operations on bipartite graphs as well as a forgetful operation which constructs its underlying graph. With this in mind we are ready to present the algorithm.

A fast implementation of the simple method for vertices can be done in any software which can check whether a collection of sets is nested. Having introduced the algorithm we will now show that it successfully detects whether or not the graph is 2-chordal bipartite. We claim that the graph successfully checks (i) and (ii) of Theorem 3.1.

We first look at the intuition behind this theorem. Property (ii) is not sufficient alone as we could have a graph which was entirely a cycle of size 6. In this hypothetical graph $G$, the modified graph $G_{e}$ would satisfy (ii) for any $e\in E(G)$ as it contains no cycles. However, the original graph $G$ clearly fails to be chordal bipartite let alone 2-chordal bipartite. With the addition of (i), we guarantee that any cycle of size 6 or more contains at least one chord. As we iterate over the edges of the graph in (ii), we encounter this chord and our modified graph contains the same cycle, but with one fewer chords. Therefore if the modified graph is chordal bipartite, it must contain a second chord.

Theorem 3.1 has a natural generalization to $k$-chordal bipartite graphs.

We allow 0-chordal bipartite to be a vacuous truth of all graphs so that Theorem 4.3. is valid for all $k\in{\mathbb{N}}$. We call an $k$-chordal bipartite graph trivial if it contains no cycles of length 6 or greater. The proof of this theorem mirrors the 2-chordal bipartite case.

There is an important bound on the minimum cycle size for nontrivial $k$-chordal bipartite graphs for large $n$.

This can easily be seen by noting that a cycle of size 6 is constructed from two sets of three vertices and can at most admit three chords, as shown in Figure 5.

Our attention now turns to the efficiency of the problem. Algorithm 1 is a naive implementation in that faster means of checking whether a graph is strongly chordal are known, in fact it can checked via the construction of a strong perfect elimination ordering. This construction is related to the problem of doubly lexical orderings of matrices and can be performed in time $O(\min(s^{2},(s+t)\log s))$ where $s$ is the cardinality of the vertex set and $t$ is the cardinality of the edge set [8] [9]. This allows us to check that a bipartite graph is chordal bipartite in $O(\min(s^{2},(2s+t)\log(s))=O(\min(s^{2},(s+t)\log s)$ time (as a graph is chordal bipartite if and only if the graph obtained by adding an edge between every pair of vertices in one of its partitions is strongly chordal). Thus, the decision problem is in complexity class P. The algorithm for determining whether a bipartite graph is 2-chordal bipartite amounts to iterating the chordal bipartite algorithm over the edge set of the bipartite graph. Within the loop the subgraph has one fewer edge but the same number of vertices.

Going a bit further, it’s reasonable to assume that $D_{s,t}$ is negligible compared to the other operations and that $t>1$, in which case the above is $O(\min\{ts^{2},t(s+t-1)\log s)$. In other words, the process is as efficient as possible with the current characterization of 2-chordal bipartite graphs offered here. Like the $2$-chordal bipartite problem, the $3$-chordal bipartite problem, and the general $k$-chordal bipartite problem, is polynomial in complexity on the vertex set alone and its runtime can be found by iterating this process giving

under the mild assumptions given above. A small corollary of Theorem 5.1 is that the induced subgraph problem for the double square graph is also in P.