I am looking for websites or articles where can I find a data with test graphs for domination set problem. In my heuristic algorithms I use undirected and unweighted graphs. So I search for some graphs which already have been tested from other people.

  • 3
    $\begingroup$ I cannot see any research level statement in the question, but on the other hand when I saw a question I did a google search to see if deserves to downvote, but I didn't find any reference as requested (in quick search), so I think while the question is not well explained, it's also not very welcome to downvote a new user without any explanation. $\endgroup$
    – Saeed
    Apr 8, 2014 at 12:38
  • 1
    $\begingroup$ You can search hard instances of problems which can be easily reduced to dominating set. For example search "DIMACS graph benchmarks vertex cover". $\endgroup$ Apr 8, 2014 at 13:59
  • $\begingroup$ @MarzioDeBiasi, That's a good idea, then may be is not bad to explain it in more details as answer (e.g by mentioning that it's approximation or heuristic preserving reduction), e.g I personally had no idea about the good search term for the case that OP looking for, but your suggestion seems to be nice. Well, as I said question is not well explained and we don't know what is the OP's algorithm (approximation, heuristic, exact), but your suggestion is nice anyway. $\endgroup$
    – Saeed
    Apr 8, 2014 at 14:07
  • $\begingroup$ @Saeed: I'll wait OP's clarifications :) $\endgroup$ Apr 8, 2014 at 14:25
  • 4
    $\begingroup$ This is a serious research question. Many query complexity problems can be formulated as DOM sets. I had to roll my own C code for MinDomSet. Any recommendation would be appreciated. $\endgroup$ Apr 8, 2014 at 14:38

1 Answer 1


A quick google search revealed Experiments on Data Reduction for Optimal Domination in Networks. If you look at their tables they cite a number of data sets for which the actual dominating set is given. They also use a number of random graph generators and publish the average dominating set size for these.

There's another paper from 2002: Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem. I couldn't find an online copy, but I'm sure this paper also documents data sets and actual DS sizes.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.