Haraguchi, Kazuya
An Efficient Local Search for the Minimum Independent Dominating Set Problem
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 kswap 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 2swap), 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 nonsolution vertex. The algorithm is so effective that, among 80 DIMACS graphs, it updates the bestknown solution size for five graphs and performs as well as existing methods for the remaining graphs.
BibTeX  Entry
@InProceedings{haraguchi:LIPIcs:2018:8948,
author = {Kazuya Haraguchi},
title = {{An Efficient Local Search for the Minimum Independent Dominating Set Problem}},
booktitle = {17th International Symposium on Experimental Algorithms (SEA 2018)},
pages = {13:113:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770705},
ISSN = {18688969},
year = {2018},
volume = {103},
editor = {Gianlorenzo D'Angelo},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8948},
URN = {urn:nbn:de:0030drops89484},
doi = {10.4230/LIPIcs.SEA.2018.13},
annote = {Keywords: Minimum independent dominating set problem, local search, plateau search, metaheuristics}
}
19.06.2018
Keywords: 

Minimum independent dominating set problem, local search, plateau search, metaheuristics 
Seminar: 

17th International Symposium on Experimental Algorithms (SEA 2018)

Issue date: 

2018 
Date of publication: 

19.06.2018 
Supplementary Material: 

The source code of the proposed algorithm is written in C++ and available at http://puzzle.haraguchis.otaruuc.ac.jp/minids/. 