On the Complexity of Directed Intersection Representation of {DAGs}

Motivated by the study of networks of web-pages generated by their information content, Kostochka et al. [ISIT 2019] introduced a novel notion of directed intersection representation of a (acyclic) directed graph and studied the problem of determining the directed intersection number of a digraph D, henceforth denoted by DIN(D), defined as the minimum cardinality of a ground set such that it is possible to assign to each vertex a subset such that if and only if the following two conditions hold: (i); (ii). In this paper we show that determining DIN(D) is NP-hard. We also show a 2-approximation algorithm for arborescences.