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.
On the Complexity of Directed Intersection Representation of {DAGs}
Andrea Caucchiolo;Ferdinando Cicalese
2020-01-01
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
Din-COCOON2020-cameraready.pdf
solo utenti autorizzati
Tipologia:
Documento in Post-print
Licenza:
Copyright dell'editore
Dimensione
515.24 kB
Formato
Adobe PDF
|
515.24 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.