Barbero, Florian ;
Isenmann, Lucas ;
Thiebaut, Jocelyn
On the Distance Identifying Set MetaProblem and Applications to the Complexity of Identifying Problems on Graphs
Abstract
Numerous problems consisting in identifying vertices in graphs using distances are useful in domains such as network verification and graph isomorphism. Unifying them into a metaproblem may be of main interest. We introduce here a promising solution named Distance Identifying Set. The model contains Identifying Code (IC), Locating Dominating Set (LD) and their generalizations rIC and rLD where the closed neighborhood is considered up to distance r. It also contains Metric Dimension (MD) and its refinement rMD in which the distance between two vertices is considered as infinite if the real distance exceeds r. Note that while IC = 1IC and LD = 1LD, we have MD = inftyMD; we say that MD is not local.
In this article, we prove computational lower bounds for several problems included in Distance Identifying Set by providing generic reductions from (Planar) Hitting Set to the metaproblem. We focus on two families of problem from the metaproblem: the first one, called bipartite gifted local, contains rIC, rLD and rMD for each positive integer r while the second one, called 1layered, contains LD, MD and rMD for each positive integer r. We have:
 the 1layered problems are NPhard even in bipartite apex graphs,
 the bipartite gifted local problems are NPhard even in bipartite planar graphs,
 assuming ETH, all these problems cannot be solved in 2^{o(sqrt{n})} when restricted to bipartite planar or apex graph, respectively, and they cannot be solved in 2^{o(n)} on bipartite graphs,
 even restricted to bipartite graphs, they do not admit parameterized algorithms in 2^{O(k)} * n^{O(1)} except if W[0] = W[2]. Here k is the solution size of a relevant identifying set.
In particular, Metric Dimension cannot be solved in 2^{o(n)} under ETH, answering a question of Hartung in [Sepp Hartung and André Nichterlein, 2013].
BibTeX  Entry
@InProceedings{barbero_et_al:LIPIcs:2019:10211,
author = {Florian Barbero and Lucas Isenmann and Jocelyn Thiebaut},
title = {{On the Distance Identifying Set MetaProblem and Applications to the Complexity of Identifying Problems on Graphs}},
booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
pages = {10:110:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770842},
ISSN = {18688969},
year = {2019},
volume = {115},
editor = {Christophe Paul and Michal Pilipczuk},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10211},
URN = {urn:nbn:de:0030drops102114},
doi = {10.4230/LIPIcs.IPEC.2018.10},
annote = {Keywords: identifying code, resolving set, metric dimension, distance identifying set, parameterized complexity, Whierarchy, metaproblem, hitting set}
}
05.02.2019
Keywords: 

identifying code, resolving set, metric dimension, distance identifying set, parameterized complexity, Whierarchy, metaproblem, hitting set 
Seminar: 

13th International Symposium on Parameterized and Exact Computation (IPEC 2018)

Issue date: 

2019 
Date of publication: 

05.02.2019 