IDEAS home Printed from https://ideas.repec.org/a/hin/complx/1035974.html
   My bibliography  Save this article

Reachability Analysis of Low-Order Discrete State Reaction Networks Obeying Conservation Laws

Author

Listed:
  • Gergely Szlobodnyik
  • Gábor Szederkényi

Abstract

In this paper we study the reachability problem of sub- and superconservative discrete state chemical reaction networks (d-CRNs). It is known that a subconservative network has bounded reachable state space, while that of a superconservative one is unbounded. The reachability problem of superconservative reaction networks is traced back to the reachability of subconservative ones. We consider network structures composed of reactions having at most one input and one output species beyond the possible catalyzers. We give a proof that, assuming all the reactions are charged in the initial and target states, the reachability problems of sub- and superconservative reaction networks are equivalent to the existence of nonnegative integer solution of the corresponding d-CRN state equations. Using this result, the reachability problem is reformulated as an Integer Linear Programming (ILP) feasibility problem. Therefore, the number of feasible trajectories satisfying the reachability relation can be counted in polynomial time in the number of species and in the distance of initial and target states, assuming fixed number of reactions in the system.

Suggested Citation

  • Gergely Szlobodnyik & Gábor Szederkényi, 2019. "Reachability Analysis of Low-Order Discrete State Reaction Networks Obeying Conservation Laws," Complexity, Hindawi, vol. 2019, pages 1-13, March.
  • Handle: RePEc:hin:complx:1035974
    DOI: 10.1155/2019/1035974
    as

    Download full text from publisher

    File URL: http://downloads.hindawi.com/journals/8503/2019/1035974.pdf
    Download Restriction: no

    File URL: http://downloads.hindawi.com/journals/8503/2019/1035974.xml
    Download Restriction: no

    File URL: https://libkey.io/10.1155/2019/1035974?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Alexander I. Barvinok, 1994. "A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension is Fixed," Mathematics of Operations Research, INFORMS, vol. 19(4), pages 769-779, November.
    2. H. W. Lenstra, 1983. "Integer Programming with a Fixed Number of Variables," Mathematics of Operations Research, INFORMS, vol. 8(4), pages 538-548, November.
    3. Stephen Smith & Ramon Grima, 2018. "Single-cell variability in multicellular organisms," Nature Communications, Nature, vol. 9(1), pages 1-8, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Friedrich Eisenbrand & Gennady Shmonin, 2008. "Parametric Integer Programming in Fixed Dimension," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 839-850, November.
    2. Sascha Kurz & Nikolas Tautenhahn, 2013. "On Dedekind’s problem for complete simple games," International Journal of Game Theory, Springer;Game Theory Society, vol. 42(2), pages 411-437, May.
    3. Matthias Köppe & Christopher Thomas Ryan & Maurice Queyranne, 2011. "Rational Generating Functions and Integer Programming Games," Operations Research, INFORMS, vol. 59(6), pages 1445-1460, December.
    4. Jesús A. De Loera & Raymond Hemmecke & Matthias Köppe & Robert Weismantel, 2006. "Integer Polynomial Optimization in Fixed Dimension," Mathematics of Operations Research, INFORMS, vol. 31(1), pages 147-153, February.
    5. Le Breton, Michel & Lepelley, Dominique & Smaoui, Hatem, 2012. "The Probability of Casting a Decisive Vote: From IC to IAC trhough Ehrhart's Polynomials and Strong Mixing," IDEI Working Papers 722, Institut d'Économie Industrielle (IDEI), Toulouse.
    6. M. Köppe & M. Queyranne & C. T. Ryan, 2010. "Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs," Journal of Optimization Theory and Applications, Springer, vol. 146(1), pages 137-150, July.
    7. K. Aardal & R. E. Bixby & C. A. J. Hurkens & A. K. Lenstra & J. W. Smeltink, 2000. "Market Split and Basis Reduction: Towards a Solution of the Cornuéjols-Dawande Instances," INFORMS Journal on Computing, INFORMS, vol. 12(3), pages 192-202, August.
    8. Sylvain Béal & Marc Deschamps & Mostapha Diss & Issofa Moyouwou, 2022. "Inconsistent weighting in weighted voting games," Public Choice, Springer, vol. 191(1), pages 75-103, April.
    9. Alberto Del Pia & Robert Hildebrand & Robert Weismantel & Kevin Zemmer, 2016. "Minimizing Cubic and Homogeneous Polynomials over Integers in the Plane," Mathematics of Operations Research, INFORMS, vol. 41(2), pages 511-530, May.
    10. Abdelhalim El Ouafdi & Dominique Lepelley & Hatem Smaoui, 2020. "Probabilities of electoral outcomes: from three-candidate to four-candidate elections," Theory and Decision, Springer, vol. 88(2), pages 205-229, March.
    11. Klaus Jansen & Roberto Solis-Oba, 2011. "A Polynomial Time OPT + 1 Algorithm for the Cutting Stock Problem with a Constant Number of Object Lengths," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 743-753, November.
    12. Elizabeth Baldwin & Paul Klemperer, 2019. "Understanding Preferences: “Demand Types”, and the Existence of Equilibrium With Indivisibilities," Econometrica, Econometric Society, vol. 87(3), pages 867-932, May.
    13. Hatem Smaoui & Dominique Lepelley & Issofa Moyouwou, 2016. "Borda elimination rule and monotonicity paradoxes in three-candidate elections," Economics Bulletin, AccessEcon, vol. 36(3), pages 1722-1728.
    14. Jaykrishnan, G. & Levin, Asaf, 2024. "Scheduling with cardinality dependent unavailability periods," European Journal of Operational Research, Elsevier, vol. 316(2), pages 443-458.
    15. Masing, Berenike & Lindner, Niels & Borndörfer, Ralf, 2022. "The price of symmetric line plans in the Parametric City," Transportation Research Part B: Methodological, Elsevier, vol. 166(C), pages 419-443.
    16. Sanchari Deb & Kari Tammi & Karuna Kalita & Pinakeswar Mahanta, 2018. "Review of recent trends in charging infrastructure planning for electric vehicles," Wiley Interdisciplinary Reviews: Energy and Environment, Wiley Blackwell, vol. 7(6), November.
    17. Kenneth J. Arrow & Timothy J. Kehoe, 1994. "Distinguished Fellow: Herbert Scarf's Contributions to Economics," Journal of Economic Perspectives, American Economic Association, vol. 8(4), pages 161-181, Fall.
    18. Kubale, Marek, 1996. "Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors," European Journal of Operational Research, Elsevier, vol. 94(2), pages 242-251, October.
    19. Matthias Bentert & Robert Bredereck & Péter Györgyi & Andrzej Kaczmarczyk & Rolf Niedermeier, 2023. "A multivariate complexity analysis of the material consumption scheduling problem," Journal of Scheduling, Springer, vol. 26(4), pages 369-382, August.
    20. Danny Nguyen & Igor Pak, 2020. "The Computational Complexity of Integer Programming with Alternations," Mathematics of Operations Research, INFORMS, vol. 45(1), pages 191-204, February.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:hin:complx:1035974. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Mohamed Abdelhakeem (email available below). General contact details of provider: https://www.hindawi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.