Komusiewicz, Christian ;
Morawietz, Nils
Finding 3SwapOptimal Independent Sets and Dominating Sets Is Hard
Abstract
For PLScomplete local search problems, there is presumably no polynomialtime algorithm which finds a locally optimal solution, even though determining whether a solution is locally optimal and replacing it by a better one if this is not the case can be done in polynomial time.
We study local search for Weighted Independent Set and Weighted Dominating Set with the 3swap neighborhood. The 3swap neighborhood of a vertex set S in G is the set of vertex sets which can be obtained from S by exchanging at most three vertices. We prove the following dichotomy: On the negative side, the problem of finding a 3swapoptimal independent set or dominating set is PLScomplete. On the positive side, locally optimal independent sets or dominating sets can be found in polynomial time when allowing all 3swaps except a) the swaps that remove two vertices from the current solution and add one vertex to the solution or b) the swaps that remove one vertex from the current solution and add two vertices to the solution.
BibTeX  Entry
@InProceedings{komusiewicz_et_al:LIPIcs.MFCS.2022.66,
author = {Komusiewicz, Christian and Morawietz, Nils},
title = {{Finding 3SwapOptimal Independent Sets and Dominating Sets Is Hard}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {66:166:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772563},
ISSN = {18688969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16864},
URN = {urn:nbn:de:0030drops168644},
doi = {10.4230/LIPIcs.MFCS.2022.66},
annote = {Keywords: Local Search, Graph problems, 3swap neighborhood, PLScompleteness}
}
22.08.2022
Keywords: 

Local Search, Graph problems, 3swap neighborhood, PLScompleteness 
Seminar: 

47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Issue date: 

2022 
Date of publication: 

22.08.2022 