We show that, for acyclic graphs, considering the width of the graph yields advances in our understanding of MFD approximability. For the version of the problem that uses only non-negative weights, we identify and characterise a new class of width-stable graphs, for which a popular heuristic is a $O(\log Val(X))$-approximation ($Val(X)$ being the total flow of $X$), and strengthen its worst-case approximation ratio from $\Omega(\sqrt{m})$ to $\Omega(m/\log{m})$ for sparse graphs. We also study a new problem on graphs with cycles, Minimum Cost Circulation Decomposition (MCCD), and show that it generalises MFD through a simple reduction. For the version allowing also negative weights, we give a $(\lceil \log ||X|| \rceil + 1)$-approximation ($||X||$ being the maximum absolute value of $X$ on any edge) using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary circulations ($||X||\le 1$), using a generalised notion of width for this problem.

We provide a $O(|\delta| \log |Q|)$-time algorithm computing a co-lex total preorder when the input is a Wheeler NFA, and an algorithm with the same time complexity computing the smallest-width co-lex partial order of any DFA.

A minimum chain cover (MCC) of a $k$-width directed acyclic graph (DAG) $G = (V, E)$ is a set of $k$ chains (paths in the transitive closure) of $G$ such that every vertex appears in at least one chain in the cover. We present an algorithm running in time $O(T_{MF}(|E|) + (|V|+|E|)\log{k})$.

We present the first parameterized algorithms for SMLG in DAGs, derived from a generalization of the Knuth-Morris-Pratt algorithm optimized to work in time proportional to the number of prefix-incomparable matches. We obtain parameterizations in the topological structure of $G$, by studying a special class of DAGs called funnels and generalizing them to $k$-funnels and the class $ST_k$.

We show that, for acyclic graphs, considering the width of the graph yields advances in our understanding of its approximability. For the non-negative version, we show that a popular heuristic is a $O( \log |X|)$-approximation on graphs satisfying two properties related to the width (satisfied by e.g., series-parallel graphs), and strengthen its worst-case approximation ratio for sparse graphs. For the negative version, we give a $(\lceil \log \Vert X \Vert \rceil +1)$-approximation using a power-of-two approach, combined with parity fixing arguments and a decomposition of unitary flows ($\Vert X \Vert \leq 1$) into at most width paths.

We give the first local characterization of safe paths for flow decompositions in directed acyclic graphs (DAGs), leading to a practical algorithm for finding the complete set of safe paths. We additionally evaluated our algorithms against the trivial safe algorithms (unitigs, extended unitigs) and the popularly used heuristic (greedy-width) for flow decomposition on RNA transcripts datasets. We find that despite maintaining perfect precision the safe and complete algorithm reports significantly higher coverage as compared to trivial safe algorithms.

We obtain two new MPC parameterized algorithms for DAGs running in time $O(k^2|V|\log(|V|) + |E|)$ and $O(k^3|V| + |E|)$. We also obtain a parallel algorithm running in $O(k^2|V| + |E|)$ parallel steps and using $O(\log(|V|))$ processors (in the PRAM model). We also obtain edge sparsification algorithms preserving the width of the DAG with the same running time as our MPC algorithms.