Minimizing External Vertices in Hypergraph Orientations | SpringerLink
Skip to main content
Springer Nature Link
Log in

Minimizing External Vertices in Hypergraph Orientations

  • Conference paper
  • First Online:
Combinatorial Optimization (ISCO 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14594))

Included in the following conference series:

Abstract

We introduce the problem of assigning a direction to the hyperedges of a hypergraph such that the number of source and sink vertices is minimized. We consider hypergraphs whose hyperedges are partitioned in two disjoint subsets of vertices, which will become the tail and the head of the hyperedge when oriented. We prove that the problem is NP-hard even when restricted to hypergraphs where each vertex belongs to exactly two hyperedges, and that it becomes polynomial-time solvable on graphs. We give a compact ILP formulation for the general problem, and apply it to the biochemical reactions stored in the KEGG database by representing compounds as vertices, reactions as hyperedges, and metabolic pathways and networks as hypergraphs. We provide experimental results showing that metabolic pathways and networks with thousands of compounds and reactions can be oriented in a few seconds on a personal computer.

Supported by the Ministerio de Ciencia e Innovación (MCI), the Agencia Estatal de Investigación (AEI) and the European Regional Development Fund (ERDF) through project METACIRCLE PID2021-126114NB-C44, and by the Agency for Management of University and Research Grants (AGAUR) through grant 2021-SGR-01419 (ALBCOM).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 7550
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 10581
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Asahiro, Y., Jansson, J., Miyano, E., Ono, H.: Degree-constrained graph orientation: maximum satisfaction and minimum violation. Theory Comput. Syst. 58(1), 60–93 (2016). https://doi.org/10.1007/s00224-014-9565-5

    Article  MathSciNet  Google Scholar 

  2. Deville, Y., Gilbert, D., van Helden, J., Wodak, S.J.: An overview of data models for the analysis of biochemical pathways. Brief. Bioinform. 4(3), 246–259 (2003). https://doi.org/10.1093/bib/4.3.246

    Article  Google Scholar 

  3. Ebert, J.: Computing Eulerian trails. Inf. Process. Lett. 28(2), 93–97 (1988). https://doi.org/10.1016/0020-0190(88)90170-6

    Article  MathSciNet  Google Scholar 

  4. Edmonds, J., Johnson, E.L.: Matching, Euler tours and the Chinese postman. Math. Program. 5(1), 88–124 (1973). https://doi.org/10.1007/BF01580113

    Article  MathSciNet  Google Scholar 

  5. Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL: A Modeling Language for Mathematical Programming, 2nd edn. Cengage Learning, Boston, Massachusetts (2002)

    Google Scholar 

  6. Frank, A., Király, T., Király, Z.: On the orientation of graphs and hypergraphs. Discret. Appl. Math. 131(2), 385–400 (2003). https://doi.org/10.1016/S0166-218X(02)00462-6

    Article  MathSciNet  Google Scholar 

  7. Gallo, G., Longo, G., Pallottino, S., Nguyen, S.: Directed hypergraphs and applications. Discret. Appl. Math. 42(2–3), 177–201 (1993). https://doi.org/10.1016/0166-218X(93)90045-P

    Article  MathSciNet  Google Scholar 

  8. Garrett, R.H., Grisham, C.M.: Biochemistry, 7th edn. Cengage Learning, Boston, Massachusetts (2017)

    Google Scholar 

  9. van Helden, J., Wernisch, L., Gilbert, D., Wodak, S.J.: Graph-based analysis of metabolic networks. In: Mewes, H.W., Seidel, H., Weiss, B. (eds.) Bioinformatics and Genome Analysis. Ernst Schering Research Foundation Workshop, vol. 38, pp. 245–274. Springer, Heidelberg (2002). https://doi.org/10.1007/978-3-662-04747-7_12

    Chapter  Google Scholar 

  10. Huss, M., Holme, P.: Currency and commodity metabolites: their identification and relation to the modularity of metabolic networks. IET Syst. Biol. 1(5), 280–285 (2007). https://doi.org/10.1049/iet-syb:20060077

    Article  Google Scholar 

  11. Judge, A., Dodd, M.S.: Metabolism. Essays Biochem. 64(4), 607–647 (2020). https://doi.org/10.1042/EBC20190041

    Article  Google Scholar 

  12. Kanehisa, M., Furumichi, M., Sato, Y., Kawashima, M., Ishiguro-Watanabe, M.: KEGG for taxonomy-based analysis of pathways and genomes. Nucleic Acids Res. 51(D1), D587–D592 (2023). https://doi.org/10.1093/nar/gkac963

    Article  Google Scholar 

  13. Kennelly, P.J., Botham, K.M., McGuinness, O.P., Rodwell, V.W., Weil, P.A.: Harper’s Illustrated Biochemistry, 32nd edn. McGraw Hill, New York, NY (2023)

    Google Scholar 

  14. Khoshkhah, K.: On finding orientations with the fewest number of vertices with small out-degree. Discret. Appl. Math. 194(1), 163–166 (2015). https://doi.org/10.1016/j.dam.2015.05.007

    Article  MathSciNet  Google Scholar 

  15. Lougee-Heimer, R.: The Common Optimization INterface for operations research: promoting open-source software in the operations research community. IBM J. Res. Dev. 47(1), 57–66 (2003). https://doi.org/10.1147/rd.471.0057

    Article  Google Scholar 

  16. Ma, H.W., Zeng, A.P.: Reconstruction of metabolic network from genome information and its structural and functional analysis. In: Kriete, A., Eils, R. (eds.) Computational Systems Biology: From Molecular Mechanisms to Disease, chap. 7, pp. 113–131. Academic Press, San Diego, CA, 2nd edn. (2014). https://doi.org/10.1016/B978-0-12-405926-9.00007-1

  17. Mendoza, S.N., Olivier, B.G., Molenaar, D., Teusink, B.: A systematic assessment of current genome-scale metabolic reconstruction tools. Genome Biol. 20, 158 (2019). https://doi.org/10.1186/s13059-019-1769-1

    Article  Google Scholar 

  18. Michal, G., Schomburg, D. (eds.): Biochemical Pathways: An Atlas of Biochemistry and Molecular Biology, 2nd edn. Wiley, Hoboken (2012)

    Google Scholar 

  19. Pearcy, N., Crofts, J.J., Chuzhanova, N.: Hypergraph models of metabolism. Int. J. Bioeng. Life Sci. 8(8), 829–833 (2014). https://doi.org/10.5281/zenodo.1094247

    Article  Google Scholar 

  20. Venkateswaran, V.: Minimizing maximum indegree. Discret. Appl. Math. 143(1–3), 374–378 (2004). https://doi.org/10.1016/j.dam.2003.07.007

    Article  MathSciNet  Google Scholar 

  21. Yannakakis, M.: Node-and edge-deletion NP-complete problems. In: Lipton, R.J., Burkhard, W., Savitch, W., Friedman, E.P., Aho, A. (eds.) Proc. 10th Annual ACM Symposium on Theory of Computing, pp. 253–264. Association for Computing Machinery, New York, NY (1978). https://doi.org/10.1145/800133.804355

Download references

Acknowledgment

We thank Flavia Bonomo, Mercè Llabrés, Dora Tilli and Zephyr Verbist for detailed comments on a preliminary version of this paper.

Author information

Authors and Affiliations

  1. Universidad Nacional de Rosario, Rosario, Argentina

    Alberto José Ferrari, Valeria Leoni & Graciela Nasini

  2. CONICET, Rosario, Argentina

    Valeria Leoni & Graciela Nasini

  3. Algorithms, Bioinformatics, Complexity and Formal Methods Research Group, Technical University of Catalonia, Barcelona, Spain

    Gabriel Valiente

Authors
  1. Alberto José Ferrari
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Valeria Leoni
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Graciela Nasini
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Gabriel Valiente
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gabriel Valiente .

Editor information

Editors and Affiliations

  1. Johns Hopkins University, Baltimore, MD, USA

    Amitabh Basu

  2. Paris Dauphine University, Paris, France

    Ali Ridha Mahjoub

  3. Universidad de La Laguna, Tenerife, Spain

    Juan José Salazar González

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Ferrari, A.J., Leoni, V., Nasini, G., Valiente, G. (2024). Minimizing External Vertices in Hypergraph Orientations. In: Basu, A., Mahjoub, A.R., Salazar González, J.J. (eds) Combinatorial Optimization. ISCO 2024. Lecture Notes in Computer Science, vol 14594. Springer, Cham. https://doi.org/10.1007/978-3-031-60924-4_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-60924-4_10

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-60923-7

  • Online ISBN: 978-3-031-60924-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation