2026-07-21T20:02:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25156 2026-02-09T08:17:59Z ddc:004 open_access

A Note on the Parameterised Complexity of Coverability in Vector Addition Systems Pilipczuk, Michał Schmitz, Sylvain Sinclair-Banks, Henry vector addition system Petri net parameterised complexity coverability We investigate the parameterised complexity of the classic coverability problem for vector addition systems (VAS): V ⊆ ℤ^d, an initial configuration s ∈ ℕ^d, and a target configuration t ∈ ℕ^d, decide whether starting from s, one can iteratively add vectors from V to ultimately arrive at a configuration that is larger than or equal to t on every coordinate, while not observing any negative value on any coordinate along the way. We consider two natural parameters for the problem: the dimension d and the size of V, defined as the total bitsize of its encoding. We present several results charting the complexity of those two parameterisations, among which the highlight is that coverability for VAS parameterised by the dimension and with all the numbers in the input encoded in unary is complete for the class XNL under PL-reductions. We also discuss open problems in the topic, most notably the question about fixed-parameter tractability for the parameterisation by the size of V. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michał Pilipczuk and Sylvain Schmitz and Henry Sinclair-Banks 2025 Is Part Of LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2025.24 urn:nbn:de:0030-drops-251563 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.24 eng https://creativecommons.org/licenses/by/4.0/legalcode