<p>I need a fast min-dominating-set code for some complexity lower bounds research I am doing.</p>

<p>I could transform to SAT and use an off the shelf SAT solver; but I was hoping min-dom-set had something out there comparable to <a href="http://users.aalto.fi/~pat/cliquer.html" rel="nofollow">Cliquer</a> for max-clique.</p>

<p>Suggestions?</p>

<p>--Update--
Currently using Z3 SMT Optimize Python bindings subject to minimizing sum of dominating vertices. 0 = default, 1 = dominating. Sum of vertex and neighborhood must be >= 1 for each vertex. <a href="https://github.com/0vercl0k/z3-playground/blob/master/graph_optimization_z3.py" rel="nofollow">Here is the source code</a>.</p>

CC BY-SA 3.0
2016-02-21T19:26:14.377Z
You might want to look at SMT solvers as well.
Kaveh
CC BY-SA 3.0
2016-02-21T20:19:20.870Z
I'm fine shelling out to an SMT solver also. I would love it if anybody had a script that reduced directed graphs into SMT-LIB MIN-DOM-SET formulations.
Chad Brewbaker
CC BY-SA 3.0
2016-02-21T20:23:46.017Z
Here is a Python formulation for graph coloring using SMT-LIB solvers as a back end, https://github.com/0vercl0k/z3-playground/blob/master/graph_coloring_z3.py
Chad Brewbaker
CC BY-SA 3.0
2016-02-24T05:21:05.580Z
My first inclination would be to use a commercial Integer Programming solver like Gurobi. If you're working from a university IP address, you can get a free academic license.
Austin Buchanan
CC BY-SA 3.0
2016-02-24T05:32:01.060Z
Nah. I want it all open source.
Chad Brewbaker
<np-hardness><software>
Min dominating set software
Chad Brewbaker
# Min dominating set software

(Asked by: username_0 on 2016-02-21)

I need a fast min-dominating-set code for some complexity lower bounds research I am doing.

I could transform to SAT and use an off the shelf SAT solver; but I was hoping min-dom-set had something out there comparable to [Cliquer](http://users.aalto.fi/~pat/cliquer.html) for max-clique.

Suggestions?

--Update--
Currently using Z3 SMT Optimize Python bindings subject to minimizing sum of dominating vertices. 0 = default, 1 = dominating. Sum of vertex and neighborhood must be >= 1 for each vertex. [Here is the source code](https://github.com/0vercl0k/z3-playground/blob/master/graph_optimization_z3.py).

**Tags:** np-hardness, software

> **Comments:**
> **username_1**: You might want to look at SMT solvers as well.  
> **username_0**: I'm fine shelling out to an SMT solver also. I would love it if anybody had a script that reduced directed graphs into SMT-LIB MIN-DOM-SET formulations.  
> **username_0**: Here is a Python formulation for graph coloring using SMT-LIB solvers as a back end, https://github.com/0vercl0k/z3-playground/blob/master/graph_coloring_z3.py  
> **username_2**: My first inclination would be to use a commercial Integer Programming solver like Gurobi. If you're working from a university IP address, you can get a free academic license.  
> **username_0**: Nah. I want it all open source.  

---

## 0 answers

