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

Problems from metric graph theory such as Metric Dimension, Geodetic Set, andStrong Metric Dimension have recently had a strong impact on the field ofparameterized complexity by being the first problems in NP to admitdouble-exponential lower bounds in the treewidth, and even in the vertex covernumber for the latter. We initiate the study of enumerating minimal solutionsets for these problems and show that they are also of great interest inenumeration. More specifically, we show that enumerating minimal resolving setsin graphs and minimal geodetic sets in split graphs are equivalent tohypergraph dualization, arguably one of the most important open problems inalgorithmic enumeration. This provides two new natural examples to a questionthat emerged in different works this last decade: for which vertex (or edge)set graph property $\Pi$ is the enumeration of minimal (or maximal) subsetssatisfying $\Pi$ equivalent to hypergraph dualization? As only very fewproperties are known to fit within this context -- namely, properties relatedto minimal domination -- our results make significant progress incharacterizing such properties, and provide new angles of approach for tacklinghypergraph dualization.  In a second step, we consider cases where our reductions do not apply, namelygraphs with no long induced paths, and show these cases to be mainly tractable.

Enumerating minimal solution sets for metric graph problems