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

We study the NP-hard Shortest Path Most Vital Edges problem arising in thecontext of analyzing network robustness. For an undirected graph with positiveinteger edge lengths and two designated vertices $s$ and $t$, the goal is todelete as few edges as possible in order to increase the length of the (new)shortest $st$-path as much as possible. This scenario has been studied from theviewpoint of parameterized complexity and approximation algorithms. Wecontribute to this line of research by providing refined computationaltractability as well as hardness results. We achieve this by a systematicinvestigation of various problem-specific parameters and their influence on thecomputational complexity. Charting the border between tractability andintractability, we also identify numerous challenges for future research.

A More Fine-Grained Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths