Rights / licenseIn Copyright - Non-Commercial Use Permitted
Induced (chord-free) cycles in binary hypercubes have many applications in computer science. The state of the art for computing such cycles relies on genetic algorithms, which are, however, unable to perform a complete search. In this paper, we propose an approach to finding a special class of induced cycles we call lean, based on an efficient propositional SAT encoding. Lean induced cycles dominate a minimum number of hypercube nodes. Such cycles have been identified in Systems Biology as candidates for stable trajectories of gene regulatory networks. The encoding enabled us to compute lean induced cycles for hypercubes up to dimension 7. We also classify the induced cycles by the number of nodes they fail to dominate, using a custom-built All-SAT solver. We demonstrate how clause filtering can reduce the number of blocking clauses by two orders of magnitude. Show more
PublisherETH, Swiss Federal Institute of Technology Zürich, Computer Systems Institute
SubjectGRAPHENALGORITHMEN + GEOMETRISCHE ALGORITHMEN (GRAPHENTHEORIE); PROGRAMS AND ALGORITHMS FOR THE SOLUTION OF SPECIAL PROBLEMS; ZYKLEN (GRAPHENTHEORIE); HYPERGRAPHEN (GRAPHENTHEORIE); CYCLES (GRAPH THEORY); PROGRAMME UND ALGORITHMEN ZUR LÖSUNG SPEZIELLER PROBLEME; GRAPH ALGORITHMS + GEOMETRIC ALGORITHMS (GRAPH THEORY); HYPERGRAPHS (GRAPH THEORY)
Organisational unit02641 - Institut für Computersysteme (ehem.) / Computer Systems Institute (former)
NotesTechnical Reports D-INFK.
MoreShow all metadata