Document Open Access Logo

On Constrained Intersection Representations of Graphs and Digraphs

Authors Ferdinando Cicalese , Clément Dallard , Martin Milanič

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.38.pdf
  • Filesize: 0.7 MB
  • 15 pages

Document Identifiers

Author Details

Ferdinando Cicalese
  • Department of Computer Science, University of Verona, Italy
Clément Dallard
  • Université d'Orléans, INSA Centre Val de Loire, LIFO EA 4022, Orléans, France
Martin Milanič
  • FAMNIT and IAM, University of Primorska, Koper, Slovenia

Funding

This work is supported in part by the Slovenian Research Agency (I0-0035, research program P1-0285, research projects J1-3001, J1-3002, J1-3003, J1-4008, J1-9110, N1-0102, and N1-0160); and the GNCS group of the Italian "Istituto Nazionale di Alta Matematica - INdAM".

Acknowledgements

We would like to thank Andrea Caucchiolo for several insightful discussions we had on some of the results contained in this paper.

Cite AsGet BibTex

Ferdinando Cicalese, Clément Dallard, and Martin Milanič. On Constrained Intersection Representations of Graphs and Digraphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.38

Abstract

We study the problem of determining minimal directed intersection representations of DAGs in a model introduced by [Kostochka, Liu, Machado, and Milenkovic, ISIT2019]: vertices are assigned color sets, two vertices are connected by an arc if and only if they share at least one color and the tail vertex has a strictly smaller color set than the head, and the goal is to minimize the total number of colors. We show that the problem is polynomially solvable in the class of triangle-free and Hamiltonian DAGs and also disclose the relationship of this problem with several other models of intersection representations of graphs and digraphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Mathematics of computing → Graph theory
Keywords
  • Directed intersection representation
  • intersection number

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Andrea Caucchiolo and Ferdinando Cicalese. On the complexity of directed intersection representation of dags. In Donghyun Kim, R. N. Uma, Zhipeng Cai, and Dong Hoon Lee, editors, Computing and Combinatorics - 26th International Conference, COCOON 2020, Atlanta, GA, USA, August 29-31, 2020, Proceedings, volume 12273 of Lecture Notes in Computer Science, pages 554-565. Springer, 2020. Google Scholar
  2. Andrea Caucchiolo and Ferdinando Cicalese. On the intractability landscape of digraph intersection representations. In Cristina Bazgan and Henning Fernau, editors, Combinatorial Algorithms - 33rd International Workshop, IWOCA 2022, Trier, Germany, June 7-9, 2022, Proceedings, volume 13270 of Lecture Notes in Computer Science, pages 270-284. Springer, 2022. Google Scholar
  3. Marek Cygan, Marcin Pilipczuk, and Michał Pilipczuk. Known algorithms for edge clique cover are probably optimal. SIAM Journal on Computing, 45(1):67-83, 2016. Google Scholar
  4. Hiroshi Era and Morimasa Tsuchiya. On intersection graphs with respect to uniform families. Utilitas Math., 37:3-11, 1990. Google Scholar
  5. Hiroshi Era and Morimasa Tsuchiya. On intersection numbers of graphs. In Graph theory, combinatorics, algorithms, and applications (San Francisco, CA, 1989), pages 545-556. SIAM, Philadelphia, PA, 1991. Google Scholar
  6. Paul Erdős, A. W. Goodman, and Louis Pósa. The representation of a graph by set intersections. Canadian Journal of Mathematics, 18:106-112, 1966. Google Scholar
  7. Uriel Feige and Joe Kilian. Zero knowledge and the chromatic number. Journal of Computer and System Sciences, 57(2):187-199, 1998. Google Scholar
  8. Harold N. Gabow. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC '83, pages 448-456, New York, NY, USA, 1983. Association for Computing Machinery. Google Scholar
  9. Alexandr V. Kostochka, Xujun Liu, Roberto Machado, and Olgica Milenkovic. Directed intersection representations and the information content of digraphs. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 1477-1481. IEEE, 2019. Google Scholar
  10. Lawrence T. Kou, Larry J. Stockmeyer, and C. K. Wong. Covering edges by cliques with regard to keyword conflicts and intersection graphs. Commun. ACM, 21(2):135-139, 1978. Google Scholar
  11. Xujun Liu, Roberto Assis Machado, and Olgica Milenkovic. Directed intersection representations and the information content of digraphs. IEEE Trans. Inform. Theory, 67(1):347-357, 2021. Google Scholar
  12. Carsten Lund and Mihalis Yannakakis. On the hardness of approximating minimization problems. J. ACM, 41(5):960-981, 1994. Google Scholar
  13. James Orlin. Contentment in graph theory: Covering graphs with cliques. Indagationes Mathematicae (Proceedings), 80(5):406-424, 1977. Google Scholar
  14. William R. Pulleyblank. FACES OF MATCHING-POLYHEDRA. ProQuest LLC, Ann Arbor, MI, 1973. Thesis (Ph.D.)-University of Waterloo (Canada). Google Scholar
  15. Norman J. Pullman. Clique coverings of graphs - a survey. In Combinatorial mathematics, X (Adelaide, 1982), volume 1036 of Lecture Notes in Math., pages 72-85. Springer, Berlin, 1983. Google Scholar
  16. Fred S. Roberts. On the mobile radio frequency assignment problem and the traffic light phasing problem. In Second International Conference on Combinatorial Mathematics (New York, 1978), volume 319 of Ann. New York Acad. Sci., pages 466-483. New York Acad. Sci., New York, 1979. Google Scholar
  17. Fred S Roberts. Applications of edge coverings by cliques. Discrete applied mathematics, 10(1):93-109, 1985. Google Scholar
  18. Alexander Schrijver. Combinatorial optimization. Polyhedra and efficiency, volume 24 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 2003. Google Scholar
  19. Morimasa Tsuchiya. On uniform intersection numbers. Ars Combin., 48:225-232, 1998. Google Scholar
  20. Matteo Zeggiotti. On the complexity of the RDIN Problem. Master’s thesis, Master’s degree in Computer Science and Engineering, University of Verona, 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact