Using Counter Machines to Find Cliques and Cycles in Graphs

Consider a directed graph equipped with counters that can be incremented and decremented over an edge. Given two nodes p and q, the reachability problem asks whether there is a path from p to q in which all counters start at zero, all counters remain non-negative throughout, and all counters end at zero. I will show that one can construct instances of the reachability problem that equate to an instance of finding a clique or to an instance of finding a cycle in a graph.

Warwick Postgraduate Colloquium in Computer Science 2023

Henry Sinclair-Banks, 24/03/23, University of Warwick (UK).