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

In the presented paper we study the Length-Bounded Cut problem for specialgraph classes as well as from a parameterized-complexity viewpoint. Here, weare given a graph $G$, two vertices $s$ and $t$, and positive integers $\beta$and $\lambda$. The task is to find a set of edges $F$ of size at most $\beta$such that every $s$-$t$-path of length at most $\lambda$ in $G$ contains someedge in $F$.  Bazgan et al. conjectured that Length-Bounded Cut admits a polynomial-timealgorithm if the input graph $G$ is a~proper interval graph. We confirm thisconjecture by showing a dynamic-programming based polynomial-time algorithm. Westrengthen the W[1]-hardness result of Dvo\v{r}\'ak and Knop. Our reduction isshorter, seems simpler to describe, and the target of the reduction hasstronger structural properties. Consequently, we give W[1]-hardness for thecombined parameter pathwidth and maximum degree of the input graph. Finally, weprove that Length-Bounded Cut is W[1]-hard for the feedback vertex number. Bothour hardness results complement known XP algorithms.

Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters