A constraint programming approach to cutset problems

A constraint programming approach to cutset problems

0.00 Avg rating0 Votes
Article ID: iaor20072584
Country: United Kingdom
Volume: 33
Issue: 10
Start Page Number: 2852
End Page Number: 2865
Publication Date: Oct 2006
Journal: Computers and Operations Research
Authors: ,
Keywords: sets, programming: constraints, graphs
Abstract:

We consider the problem of finding a cutset in a directed graph G=(V,E), i.e., a set of vertices that cuts all cycles in G. Finding a cutset of minimum cardinality is NP-hard. There exist several approximate and exact algorithms, most of them using graph reduction techniques. In this paper, we propose a constraint programming approach to cutset problems and design a global constraint for computing cutsets. This cutset constraint is a global constraint over Boolean variables associated to the vertices of a given graph and states that the subgraph restricted to the vertices having their Boolean variable set to true is acyclic. We propose a filtering algorithm based on graph contraction operations and inference of simple Boolean constraints, that has a linear time complexity in O(|E|+|V|). We discuss search heuristics based on graph properties provided by the cutset constraint, and show the efficiency of the cutset constraint on benchmarks of the literature for pure minimum cutset problems, and on an application to log-based reconciliation problems where the global cutset constraint is mixed with other Boolean constraints.

Reviews

Required fields are marked *. Your email address will not be published.