Solving Subgraph Epimorphism Problems using CLP and SAT

Abstract : In this work, we compare CLP and SAT solvers on the NP-complete problem of deciding the existence of a subgraph epimorphism between two graphs. Our interest in this variant of graph matching problem stems from the study of model reductions in systems biology, where large systems of biochemical reactions can be naturally represented by bipartite digraphs of species and reactions. In this setting, model reduction can be formalized as the existence of a sequence of vertex, species or reaction, deletion and merge operations which transforms a first reaction graph into a second graph. This problem is in turn equivalent to the existence of a subgraph (corresponding to delete operations) epimorphism (i.e. surjective homomorphism, corresponding to merge operations) from the first graph to the second. We show how subgraph epimorphism problems can be modeled as Boolean constraint satisfaction problems, and we compare CLP and SAT solvers on a large benchmark of reaction graphs from systems biology.
Type de document :
Communication dans un congrès
WCB - ninth Workshop on Constraint Based Methods for Bioinformatics, colocated with CP 2013 (2013), Sep 2013, Uppsala, Sweden. pp.67--74, 2013
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00908973
Contributeur : Sylvain Soliman <>
Soumis le : lundi 25 novembre 2013 - 15:38:29
Dernière modification le : lundi 24 septembre 2018 - 14:00:04
Document(s) archivé(s) le : lundi 3 mars 2014 - 15:46:09

Fichier

sepi.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-00908973, version 1

Collections

Citation

Steven Gay, François Fages, Francesco Santini, Sylvain Soliman. Solving Subgraph Epimorphism Problems using CLP and SAT. WCB - ninth Workshop on Constraint Based Methods for Bioinformatics, colocated with CP 2013 (2013), Sep 2013, Uppsala, Sweden. pp.67--74, 2013. 〈hal-00908973〉

Partager

Métriques

Consultations de la notice

151

Téléchargements de fichiers

190