Helsinki CS Theory Seminar: Masood Feyzbakhsh Rankooh
When
Where
Event language(s)
Speaker: Masood Feyzbakhsh Rankooh
Date: 15 October 2025
Time:14:15
Title: Propositional and Integer Programming Encodings of Acyclicity
Abstract: We will present SAT and IP encodings for enforcing acyclicity in directed graphs, focusing on two complementary methods implemented to work with off-the-shelf solvers. The first builds on the Vertex Elimination method of Tarjan and Rose (1975): using elimination graphs, we obtain compact clause/linear formulations whose size tracks structural sparsity (e.g., low elimination width), yielding strong propagation and tight LP relaxations without custom propagators. The second is a Cycle Elimination scheme that, for a chosen vertex , adds constraints guaranteeing that no directed cycle passes through ; iterating this over a set or ordering of vertices cuts all cycles and connects naturally to feedback-vertex reasoning, often excelling on denser graphs or when good pivot vertices are available. We will compare the theoretical properties and practical performance of these encodings, and sketch hybrids that combine vertex and cycle elimination based constraints for stronger SAT/IP solving.
More Information about the Helsinki CS Theory Seminar is available on the event website