Technical Program

Paper Detail

Paper Title Directed Intersection Representations and the Information Content of Digraphs
Paper IdentifierWE1.R5.1
Authors Alexandr Kostochka, Xujun Liu, Roberto Machado, Olgica Milenkovic, University of Illinois, United States
Session Information Theory Methods in Graph Theory
Location Saint Victor, Level 3
Session Time Wednesday, 10 July, 09:50 - 11:10
Presentation Time Wednesday, 10 July, 09:50 - 10:10
Manuscript  Click here to download the manuscript
Abstract Consider a directed graph (digraph) in which two user vertices are connected if and only if they share at least one unit of common information content and the head vertex has a strictly smaller content than the tail. We seek to estimate the smallest possible global information content that can explain the observed digraph topology. To address this problem, we introduce the new notion of a directed intersection representation of a digraph, and show that it is well-defined for all directed acyclic graphs (DAGs). We then proceed to describe the directed intersection number (DIN), the smallest number of information units needed to represent the DAG. Our main result is a nontrivial upper bound on the DIN number of DAGs based on the longest terminal path decomposition of the vertex set. In addition, we compute the exact values of the DIN number for several simple yet relevant families of connected DAGs and construct digraphs that have near-optimal DIN values.