An Efficient Local Search for the Minimum Independent Dominating Set Problem

DOI10.4230/LIPICS.SEA.2018.13MaRDI QIDQ5140723zbMATH OpenOpenAlexFDO

Authors Kazuya Haraguchi

Publication date 16 December 2020

Full work available at URL https://arxiv.org/abs/1802.06478

zbMATH Keywords

metaheuristicslocal searchplateau searchminimum independent dominating set problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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(nDelta)$ (resp., $O(nDelt{a}^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.

Recommendations

• Fast local search for the maximum independent set problem
• An efficient local search algorithm for minimum positive influence dominating set problem
• Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs
• On approximating the minimum independent dominating set
• A branch-and-reduce algorithm for finding a minimum independent dominating set
• A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs
• Fast algorithms for min independent dominating set
• Fast algorithms for \textsc{min independent dominating set}

Cites work

• scientific article; zbMATH DE number 3159208 (Why is no real title available?)
• scientific article; zbMATH DE number 5547826 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Approximating the minimum maximal independence number
• Exact Algorithms for Finding the Minimum Independent Dominating Set in Graphs
• Fast algorithms for min independent dominating set
• Fast local search for the maximum independent set problem
• Independent domination in graphs: A survey and recent results
• Maximum minimal vertex cover parameterized by vertex cover
• Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers
• Solving the minimum independent domination set problem in graphs by exact algorithm and greedy heuristic
• The weighted independent domination problem: ILP model and algorithmic approaches

Cited in

(5)

• A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets
• Finding 3-swap-optimal independent sets and dominating sets is hard
• Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function
• Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism
• An efficient sum query algorithm for distance-based locally dominating functions

Describes a project that uses

Uses Software

• BHOSLIB

This page was built for publication: An Efficient Local Search for the Minimum Independent Dominating Set Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5140723)