Walks of Given Length in One-Counter Systems

Consider a directed graph labelled with integer weights and a counter which starts at zero value. For a particular walk through the graph, the counter is updated by adding the integer weights sequentially, but the counter must remain non-negative throughout. In this presentation, I will introduce the problem that asks whether there exists a valid walk, of a given number of edges, from a given starting node to a given ending node. When the integer weights and the given length are encoded as integers in binary, this problem is in NP but not known to be NP-hard. I will describe a polynomial-time algorithm for this problem in the special case when the graph is a sequence of non-overlapping cycles connected by a simple path.

Warwick Postgraduate Colloquium in Computer Science 2021

Henry Sinclair-Banks, 13/12/21, University of Warwick (UK).