Hardness of Mine Sweeper Problem

There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

Abstract

Our problem \textsc{Mine Sweeper} is: given an undirected graph where some vertices have a natural number associated with them, decide whether there is a way to mark some of the non-numbered vertices such that the number in each numbered vertex is equal to the amount of its marked neighbours. We reduce \textsc{Dominating Set} problem to ours. \textsc{Dominating Set} is shown to be hard by \cite{GJ}.

Related collections

Author and article information

Journal

Publisher: Center for Open Science

Publication date (Electronic preprint): November 27 2018

Article

DOI: 10.31219/osf.io/5u7rx

SO-VID: daf5c39d-d55c-4afa-a18b-160f9aa40f55

License:

https://creativecommons.org/publicdomain/zero/1.0/legalcode

History

Data availability:

Comments

Comment on this article

scite_