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.
2020
978-3-030-58149-7
Approximation algorithms; Digraphs; Intersection number; NP-hardness
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/1074149
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact