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

Orienting the edges of an undirected graph such that the resulting digraphsatisfies some given constraints is a classical problem in graph theory, withmultiple algorithmic applications. In particular, an $st$-orientation orientseach edge of the input graph such that the resulting digraph is acyclic, and itcontains a single source $s$ and a single sink $t$. Computing an$st$-orientation of a graph can be done efficiently, and it finds notableapplications in graph algorithms and in particular in graph drawing. On theother hand, finding an $st$-orientation with at most $k$ transitive edges ismore challenging and it was recently proven to be NP-hard already when $k=0$.We strengthen this result by showing that the problem remains NP-hard even forgraphs of bounded diameter, and for graphs of bounded vertex degree. Thesecomputational lower bounds naturally raise the question about which structuralparameters can lead to tractable parameterizations of the problem. Our mainresult is a fixed-parameter tractable algorithm parameterized by treewidth.

On the Parameterized Complexity of Computing $st$-Orientations with Few Transitive Edges