This site uses cookies only for the purpose of identifying user sessions.
This is required to properly register actions.
SAT $\leq$ DOMINATING SET
Reduce the
SAT problem to the
DOMINATING SET problem.
These problems are defined as follows:
- SAT: given a boolean formula $F$ in conjunctive normal form, is $F$
satisfiable?
More formally, this problem can be defined as the following set:
$\{ F=C_1\wedge\ldots\wedge C_n \mid F\text{ satisfiable} \}$
- DOMINATING SET: given a natural $k$ and an undirected graph $G$, is
there a subset $S$ of size at most $k$ of nodes that dominates $G$? In other
words, is there a subset $S$ of nodes with size at most $k$ such that any node
of $G$ is either in $S$ or adjacent to a node in $S$?
More formally, this problem can be defined as the following set:
$\{ \langle k,G=\langle V,E\rangle\rangle \mid \exists S\subseteq V: (|S|\leq k\;\wedge\;\forall u\in V: (u\in S\;\vee\;\exists v\in S: \{u,v\}\in E)) \}$
The input and output of the reduction conform to the following data types:
Authors: Carles Creus, Pau Fernández, Guillem Godoy
/
Documentation: