On Modeling Connectedness in Reductions from Graph Problems to Extended Satisfiability
edited by: Juan Pavón, NéstorD Duque-Méndez, Rubén Fuentes-Fernández
In this paper we present an efficient way to encode connectedness in reductions from graph problems to SAT and MaxSAT. We show and prove linear reductions from Minimum Path and Clique and a quadratic reduction from Steiner Tree, although others NP-complete and NP-hard problems can be reduced with this complexity as well. These reductions use a new class of operators that extends the traditional set of connectors of propositional logic.