3
$\begingroup$

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 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.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ You might want to look at SMT solvers as well. $\endgroup$ – Kaveh Feb 21 '16 at 19:26
  • $\begingroup$ 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. $\endgroup$ – Chad Brewbaker Feb 21 '16 at 20:19
  • $\begingroup$ Here is a Python formulation for graph coloring using SMT-LIB solvers as a back end, github.com/0vercl0k/z3-playground/blob/master/… $\endgroup$ – Chad Brewbaker Feb 21 '16 at 20:23
  • $\begingroup$ 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. $\endgroup$ – Austin Buchanan Feb 24 '16 at 5:21
  • $\begingroup$ Nah. I want it all open source. $\endgroup$ – Chad Brewbaker Feb 24 '16 at 5:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.