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 a generalization of the classic Spanning Tree problem that allowsfor a non-uniform failure model. More precisely, edges are either \emph{safe}or \emph{unsafe} and we assume that failures only affect unsafe edges. InUnweighted Flexible Graph Connectivity we are given an undirected graph $G =(V,E)$ in which the edge set $E$ is partitioned into a set $S$ of safe edgesand a set $U$ of unsafe edges and the task is to find a set $T$ of at most $k$edges such that $T - \{u\}$ is connected and spans $V$ for any unsafe edge $u\in T$. Unweighted Flexible Graph Connectivity generalizes both Spanning Treeand Hamiltonian Cycle. We study Unweighted Flexible Graph Connectivity in termsof fixed-parameter tractability (FPT). We show an almost complete dichotomy onwhich parameters lead to fixed-parameter tractability and which lead tohardness. To this end, we obtain FPT-time algorithms with respect to the vertexdeletion distance to cluster graphs and with respect to the treewidth. Byexploiting the close relationship to Hamiltonian Cycle, we show that FPT-timealgorithms for many smaller parameters are unlikely under standardparameterized complexity assumptions. Regarding problem-specific parameters, weobserve that Unweighted Flexible Graph Connectivity} admits an FPT-timealgorithm when parameterized by the number of unsafe edges. Furthermore, weinvestigate a below-upper-bound parameter for the number of edges of asolution. We show that this parameter also leads to an FPT-time algorithm.

On the Complexity of Finding a Sparse Connected Spanning Subgraph in a non-Uniform Failure Model