English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Numerous problems consisting in identifying vertices in graphs usingdistances are useful in domains such as network verification and graphisomorphism. Unifying them into a meta-problem may be of main interest. Weintroduce here a promising solution named Distance Identifying Set. The modelcontains Identifying Code (IC), Locating Dominating Set (LD) and theirgeneralizations $r$-IC and $r$-LD where the closed neighborhood is consideredup to distance $r$. It also contains Metric Dimension (MD) and its refinement$r$-MD in which the distance between two vertices is considered as infinite ifthe real distance exceeds $r$. Note that while IC = 1-IC and LD = 1-LD, we haveMD = $\infty$-MD; we say that MD is not local  In this article, we prove computational lower bounds for several problemsincluded in Distance Identifying Set by providing generic reductions from(Planar) Hitting Set to the meta-problem. We mainly focus on two families ofproblem from the meta-problem: the first one, called bipartite gifted local,contains $r$-IC, $r$-LD and $r$-MD for each positive integer $r$ while thesecond one, called 1-layered, contains LD, MD and $r$-MD for each positiveinteger $r$. We have:  - the 1-layered problems are NP-hard even in bipartite apex graphs,  - the bipartite gifted local problems are NP-hard even in bipartite planargraphs,  - assuming ETH, all these problems cannot be solved in $2^{o(\sqrt{n})}$ whenrestricted to bipartite planar or apex graph, respectively, and they cannot besolved in $2^{o(n)}$ on bipartite graphs,  - even restricted to bipartite graphs, they do not admit parameterizedalgorithms in $2^{O(k)}.n^{O(1)}$ except if W[0] = W[2]. Here $k$ is thesolution 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 2013.

On the Distance Identifying Set meta-problem and applications to the complexity of identifying problems on graphs