Strongly Chordal Graph Generation using Intersection Graph Characterisation
Md. Zamilur Rahman Asish Mukhopadhyay
cs.DS math.CO

Decision Tree Learning for Uncertain 
 Clinical Measurements
    Cecília Nunes, Hélène Langet, Mathieu De Craene, Oscar Camara, Bart Bijnens, Anders Jonsson
C. Nunes, O. Camara, B. Bijnens and A. Jonsson are with the Department of Information and Communication Technologies, Universitat Pompeu Fabra, Barcelona, Spain. 

	
	
	E-mail: cecilia.nunes@upf.edu
	C. Nunes, H. Langet and M. De Craene are with Philips Research Medisys, Paris, France. B. Bijnens is with ICREA, Barcelona, Spain.
	
© 2018 IEEE.  Personal use of this material is permitted.  Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. Manuscript received August 28, 2018.

    
====================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================





§ INTRODUCTION

 


Strongly chordal graphs, introduced by Farber <cit.>, are a subclass 
of chordal graphs. He also established a number of different characterizations for this class of 
graphs. These include an intersection graph characterization <cit.> that is 
analogous to a similar characterization for chordal graphs <cit.>. Seker 
et al. <cit.> exploited this characterization of chordal graphs to obtain an algorithm for generating them. In this paper, we propose an algorithm to show that strongly chordal graphs
can also be generated using their intersection graph characterization.


The following essential definitions from Farber <cit.> underlie this 
characterization. Let r be the root T of an edge-weighted tree. The edge-weights are 
positive numbers that can be conveniently interpreted as the lengths of the edges. 



The weighted distance from a node u to a node v in T,  denoted by d_T^*(u,v), is the sum of the lengths of the edges of the (unique) path from u to v.



Let T_1 and T_2 be two subtrees of T. Subtree T_1 is full with respect to T_2, denoted by T_1>T_2, if for any two vertices u,v ∈ T_2 such that d_T^*(r,u)≤ d_T^*(r,v), v∈ V(T_1) implies that u∈ V(T_1).
 


A collection of subtrees {T_0, T_2,…, T_k - 1} of T is compatible if for each pair of 
subtrees T_i and T_j either T_i>T_j or T_j>T_i. 


Using the definitions above, Farber established the following intersection graph characterization for strongly chordal graphs. 

 <cit.>
	A graph is strongly chordal if and only if it is the intersection graph of a compatible collection of subtrees of a rooted, weighted tree, T.




§ THE ALGORITHM



Let S be an adjacency matrix whose rows correspond to a compatible collection
of subtrees, {T_0, T_2, …, T_k - 1}, of a rooted, weighted tree T as in 
Theorem <ref> and columns correspond to the vertices {v_0, v_2, …, v_n - 1} 
of T, arranged from left to right in order of non-decreasing distance from the root, r. 
Our main observation is that Definition <ref> can be re-interpreted to imply that 
the matrix S cannot have 
Δ_1 = [ [ 1 1; 0 1 ]] as a sub-matrix. 
More precisely, if i and j are two rows of S, corresponding 
to compatible subtrees T_i and T_j of T, then there cannot exist columns k and l 
that intersect these two rows to create Δ_1. 
Thus S belongs to the class of 
0-1 matrices that do not have Δ_1 as a submatrix. Note that this is only a necessary condition. If we can generate a 0-1 matrix that satisfies this necessary condition, we have to 
further ensure that each row corresponds to a subtree of a weighted tree T. The details of how 
this can be achieved are described in the algorithm below that is built atop our observation
of the forbidden sub-matrix property of S.




If we can generate the compatible collection of subtrees, then we can generate strongly chordal graph. The problem of generating a compatible collection of subtrees is the same as ensuring that a 0-1 matrix does not have Δ_1 = [ [ 1 1; 0 1 ]] as a submatrix. 


Each of the entries of the first row and the first column are randomly set to 0 or 1. 
The entries of the submatrix [1..k - 1, 1..n - 1] 

 are carefully set to 0 or 1 so as not have Δ_1 as a submatrix. 
This is done in row major order. While setting the entry of the i-th row and j-th column
we check exhaustively the entries in the columns to the left of the j-th column and the 
entries above the i-th row to make sure that no 2 × 2 submatrix is equal to Δ_1.
To have a compatible collection of subtrees {T_0, T_2,…, T_k-1} of a given tree T, we also do not want 
Δ_2 = [ [ 0 1; 1 1 ]] as a submatrix. 

Such a submatrix can create cycles in the tree T we wish to construct from the rows 
of our matrix representing a collection of compatible subtrees. Algorithm <ref> generates a 0-1 matrix S without Δ_1 or Δ_2 as a submatrix.
  



In the next phase, we prune some of the rows of S.
First, we remove rows with all 0's. Then we remove duplicate rows (if any) because they 
produce identical subtrees and denote the reduced matrix by S'. In the next step, we generate a strongly chordal graph from the matrix S'. Each subtree (row) 
represents a vertex in the strongly chordal graph, and there is an edge between two vertices in 
the strongly chordal graph if T_i∩ T_j≠∅. 
Algorithm <ref> takes the number of columns (nodes) n and the 
number of rows (subtrees) k (k≤ n) as inputs and outputs a 
strongly chordal graph G. 




In the following paragraphs, we explain on an example the strongly chordal graph generation process step-by-step. 


Example: Algorithm <ref> generates the following 0-1 matrix S with 
k = 12 and n = 12.


    S=[ 1 0 0 0 1 0 0 0 1 0 0 1; 1 0 1 0 0 0 0 1 0 1 1 0; 1 1 0 1 0 1 1 0 0 0 0 0; 1 0 1 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0; 1 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0; 1 1 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0; 0 0 0 0 0 0 0 0 0 0 0 0 ]


After removing 6 rows (row index: 4^th, 6^th, 8^th, 9^th, 10^th, 11^th) that have only zero entries, we get the following matrix S^':


    S'=[ 1 0 0 0 1 0 0 0 1 0 0 1; 1 0 1 0 0 0 0 1 0 1 1 0; 1 1 0 1 0 1 1 0 0 0 0 0; 1 0 1 0 0 0 0 0 0 0 0 0; 1 0 0 0 0 0 0 0 0 0 0 0; 1 1 0 0 0 0 0 0 0 0 0 0;   ]


From the matrix S', we can see there are six subtrees. The subtrees are shown in Figure <ref>. The strongly chordal graph shown in Figure <ref> is generated by representing each T_i of Figure <ref> as a node v_T_i. There is an edge between v_T_i and v_T_j if the intersection of T_i and T_j is non-empty. 
 

 






§ COMPLEXITY

Algorithm <ref> takes 

O(n^4) time to generate matrix S, ensuring it does not have Δ_1 or Δ_2 as a submatrix. The intersection of two subtrees (T_i∩ T_j) can be computed in O(n) time. Each subtree represents a vertex in a strongly chordal graph and if T_i∩ T_j≠∅, then there is an edge between two vertices in a strongly chordal graph. The insertion of an edge can be done in O(1) time.



§ CONCLUSIONS


To the best of our knowledge this is the first algorithm for generating strongly chordal graphs based on an intersection graph characterization of this class. It would be interesting to improve on the time-complexity of this algorithm or find a more efficient way of generating strongly chordal graphs. We implemented this proposed algorithm in Python. As a matter of curiosity, we tested a large number of intersection graphs generated from Δ_1-free matrices. Without exception, all of these passed the recognition algorithm test for strong chordality. It would be worthwhile to investigate this further. 


In this paper we present an algorithm for generating strongly chordal graphs. The algorithm is based on the characterization that a graph is strongly chordal if and only if it is the intersection graph of a compatible collection of subtrees of a rooted weighted tree.








10
	
	FarberThesis
	Martin Farber.
	Applications of 1.p. duality to problems involving independence
		and domination.
	PhD thesis, Rutgers University, 1982.
	
	DBLP:journals/dm/Farber83
	Martin Farber.
	Characterizations of strongly chordal graphs.
	Discrete Mathematics, 43(2-3):173–189, 1983.
	
	GAVRIL197447
	Fanica Gavril.
	The intersection graphs of subtrees in trees are exactly the chordal
	graphs.
	Journal of Combinatorial Theory, Series B, 16(1):47 – 56,
	1974.
	
	DBLP:journals/corr/abs-1810-13326
	Oylum Seker, Pinar Heggernes, Tinaz Ekim, and Z. Caner Taskin.
	Generation of random chordal graphs using subtrees of a tree.
	CoRR, abs/1810.13326, 2018.
	


