Document Open Access Logo

An Efficient Local Search for the Minimum Independent Dominating Set Problem

Author Kazuya Haraguchi

PDF
Thumbnail PDF

File

LIPIcs.SEA.2018.13.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Kazuya Haraguchi
  • Otaru University of Commerce, Midori 3-5-21/Otaru, Hokkaido, Japan

Cite As Get BibTex

Kazuya Haraguchi. An Efficient Local Search for the Minimum Independent Dominating Set Problem. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SEA.2018.13

Abstract

In the present paper, we propose an efficient local search for the minimum independent dominating set problem. We consider a local search that uses k-swap as the neighborhood operation. Given a feasible solution S, it is the operation of obtaining another feasible solution by dropping exactly k vertices from S and then by adding any number of vertices to it. We show that, when k=2, (resp., k=3 and a given solution is minimal with respect to 2-swap), we can find an improved solution in the neighborhood or conclude that no such solution exists in O(n Delta) (resp., O(n Delta^3)) time, where n denotes the number of vertices and Delta denotes the maximum degree. We develop a metaheuristic algorithm that repeats the proposed local search and the plateau search iteratively, where the plateau search examines solutions of the same size as the current solution that are obtainable by exchanging a solution vertex and a non-solution vertex. The algorithm is so effective that, among 80 DIMACS graphs, it updates the best-known solution size for five graphs and performs as well as existing methods for the remaining graphs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Minimum independent dominating set problem
  • local search
  • plateau search
  • metaheuristics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. D.V. Andrade, M.G.C. Resende, and R.F. Werneck. Fast local search for the maximum independent set problem. Journal of Heuristics, 18:525-547, 2012. Google Scholar
  2. C. Berge. Theory of Graphs and its Applications. Methuen, London, 1962. Google Scholar
  3. BHOSLIB: Benchmarks with hidden optimum solutions for graph problems. http://sites.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm. accessed on February 1, 2018.
  4. N. Bourgeois, F.D. Croce, B. Escoffier, and V.Th. Paschos. Fast algorithms for MIN independent dominating set. Discrete Applied Mathematics, 161(4):558-572, 2013. Google Scholar
  5. P.P. Davidson, C. Blum, and J. Lozano. The weighted independent domination problem: ILP model and algorithmic approaches. In Proc. EvoCOP 2017, pages 201-214, 2017. URL: http://dx.doi.org/10.1007/978-3-319-55453-2_14.
  6. M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman &Company, 1979. Google Scholar
  7. I.P. Gent and T. Walsh. The SAT phase transition. In Proc. ECAI-94, pages 105-109, 1994. Google Scholar
  8. W. Goddard and M.A. Henning. Independent domination in graphs: A survey and recent results. Discrete Mathematics, 313:839-854, 2013. Google Scholar
  9. C.P. Gomes and B. Selman. Problem structure in the presence of perturbations. In Proc. AAAI-97, pages 221-227, 1997. Google Scholar
  10. C.P. Gomes and D.B. Shmoys. Completing quasigroups or latin squares: a structured graph coloring problem. In Proc. Computational Symposium on Graph Coloring and Generalizations, 2002. Google Scholar
  11. M.M. Halldórsson. Approximating the minimum maximal independence number. Information Processing Letters, 46(4):169-172, 1993. Google Scholar
  12. IBM ILOG CPLEX. https://www.ibm.com/analytics/data-science/prescriptive-analytics/cplex-optimizer. accessed on February 1, 2018.
  13. F. Kuhn, T. Nieberg, T. Moscibroda, and R. Wattenhofer. Local approximation schemes for ad hoc and sensor networks. In Proc. the 2005 Joint Workshop on Foundations of Mobile Computing, pages 97-103, 2005. Google Scholar
  14. C. Laforest and R. Phan. Solving the minimum independent domination set problem in graphs by exact algorithm and greedy heuristic. RAIRO-Operations Research, 47(3):199-221, 2013. Google Scholar
  15. C. Liu and Y. Song. Exact algorithms for finding the minimum independent dominating set in graphs. In Proc. ISAAC 2006, LNCS 4288, pages 439-448, 2006. Google Scholar
  16. LocalSolver. http://www.localsolver.com/. accessed on February 1, 2018.
  17. F. Mascia. dimacs benchmark set. http://iridia.ulb.ac.be/~fmascia/maximum_clique/DIMACS-benchmark. accessed on February 1, 2018.
  18. W. Pullan. Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers. Discrete Optimization, 6(2):214-219, 2009. Google Scholar
  19. W. Pullan and H.H. Hoos. Dynamic local search for the maximum clique problem. Journal of Artificial Intelligence Research, 25:159-185, 2006. Google Scholar
  20. Y. Wang, J. Chen, H. Sun, and M. Yin. A memetic algorithm for minimum independent dominating set problem. Neural Computing and Applications, in press. URL: http://dx.doi.org/10.1007/s00521-016-2813-7.
  21. Y. Wang, R. Li, Y. Zhou, and M. Yin. A path cost-based grasp for minimum independent dominating set problem. Neural Computing and Applications, 28(1):143-151, 2017. URL: http://dx.doi.org/10.1007/s00521-016-2324-6.
  22. M. Zehavi. Maximum minimal vertex cover parameterized by vertex cover. SIAM Journal on Discrete Mathematics, 31(4):2440-2456, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact