- Introduction. The minimum flow decomposition (MFD) problem asks to decompose a directed acyclic flow network (G,f) with a unique source s and a unique sink t into the fewest weighted s-t paths whose combined contributions exactly reproduce f. MFD underlies a broad class of multi-assembly tasks in bioinformatics: reference-based RNA assembly from splice graphs [Trapnell et al., 2010; Guttman et al., 2010; Tomescu et al., 2013; Song et al., 2016; Liu et al., 2016; Pertea et al., 2015; Kovaka et al., 2019; Shao and Kingsford, 2017; Zhang et al., 2022; Tung et al., 2019], metagenomic assembly [Shaw et al., 2024], and viral quasi-species inference [Baaijens et al., 2020]. MFD is strongly NP-hard [Vatinlen et al., 2008] and hard to approximate within some fixed constant factor [Hartman et al., 2012]. Exact solvers include an FPT algorithm whose runtime grows exponentially in the solution size [Kloster et al., 2018] and a family of integer linear programming (ILP) formulations [Dias et al., 2022; Grigorjew et al., 2024] capable of handling extensions such as inexact flows [Williams et al., 2019; Dias and Tomescu, 2024], safety and subpath constraints [Williams et al., 2022; Gibney et al., 2022; Khan et al., 2022; Dias et al., 2023], and graphs with cycles [Dias et al., 2025]. However, ILP remains unscalable on large practical instances. The widely used greedy-width heuristic [Vatinlen et al., 2008] is very efficient but can be exponentially worse than optimal in the worst case [Cáceres et al., 2024]. The state-of-the-art heuristic, catfish [Shao and Kingsford, 2017], substantially improves this efficiency-performance tradeoff by identifying linear equations among edge flow values - structural constraints implied by any optimal decomposition - and resolving them via safe graph transformations. On simpler instances catfish is highly effective, but three interrelated limitations degrade its performance on complex graphs: (1) it cannot distinguish good equations (arising from a true optimal decomposition) from superficial ones that distort the graph when resolved; (2) many good equations cannot be fully resolved due to the absence of suitable closed subgraphs, so catfish discards their information entirely; and (3) when no equation is resolvable catfish falls back to greedy-width, which performs poorly on entangled graphs. - Method. We introduce catfish-LP, which augments catfish with a lightweight linear programming (LP) formulation based on saturating subflows. For each edge e ∈ E we define continuous variables {x_e(a) : a ∈ E} modeling a valid s-t subflow that saturates e; intuitively, x_e(a) represents the amount of flow on e that must passes through edge a. Five base constraints enforce saturation, symmetry, flow validity, and flow conservation. Two additional equation constraints require that the aggregate subflow through the left-hand-side edges of an equation equals that through the right-hand-side edges. The full LP is polynomial-time solvable, adding only modest overhead over catfish. The LP plays three complementary roles within a single unified framework: (1) equation filtering: if adding a candidate equation renders the LP infeasible, that equation cannot arise from any minimum decomposition and is discarded, preventing structurally invalid graph transformations; (2) safe edge merging: a feasible LP solution reveals pairs of edges that must carry identical subflow and can therefore be safely contracted; (3) informed greedy extraction: when no further simplification is possible, rather than invoking greedy-width blindly, catfish-LP extracts from the LP solution the heaviest simple path consistent with all surviving equations, deferring the error-prone greedy step as long as possible. - Experimental Results. We compare catfish-LP against greedy-width, catfish, and the optimized ILP solver [Grigorjew et al., 2024] on two benchmarks, using Gurobi [{Gurobi Optimization, 2024] as the underlying LP/ILP engine. Table 1 reports decomposition quality on four datasets of biologically derived splice graphs, with abundances estimated by Salmon [Patro et al., 2017] or simulated with the Flux-Simulator [Griebel et al., 2012]. Catfish-LP achieves the smallest excess among heuristics on the Salmon dataset and negative excess on the remaining three, matching ILP quality while being orders of magnitude faster. Figure 1 summarizes results on 1,440 simulated graphs spanning 72 complexity configurations. Catfish-LP consistently produces the smallest decompositions and recovers the most ground-truth paths among all heuristics, achieving near-ILP quality in a fraction of its runtime - including a threefold improvement over catfish on the hardest 498 instances where ILP times out on every instance. - Conclusion. Catfish-LP demonstrates that incorporating a polynomial-time LP oracle into a combinatorial heuristic yields substantial gains in decomposition quality with negligible scalability cost, addressing each of catfish’s core limitations in a unified manner. Future directions include strengthened LP formulations, domain-specific constraints for transcriptome assembly, and probabilistic interpretations of LP-guided decompositions.

As a novel network paradigm, Software Defined Networking (SDN) has greatly simplified network management, but also introduced new vulnerabilities. One vulnerability of particular interest is the flow table, a data structure in every SDN-enabled switch that caches flow rules from the controller to bridge the speed gap between the data plane and the control plane. Prior works have shown that an adversary-controlled host can accurately infer parameters of the flow table at its directly-connected edge switch, which can then be used to launch intelligent attacks. However, those solutions do not work for flow tables at internal switches. In this work, we develop an algorithm that can infer the different flow table sizes at internal switches by measuring the Round Trip Times (RTTs) of a path traversing these switches from one of its endpoints. A major challenge in this problem is the lack of an inferable relationship between the RTTs and the flow table hits/misses at the traversed switches. Our solution addresses this challenge by experimentally identifying the inferable information and designing an inference algorithm that combines carefully designed probing sequences and statistical tools to mitigate measurement noise and interference. The efficacy of our solution is validated through experiments in Mininet.

In-network caching and flexible routing are two of the most celebrated advantages of next generation network infrastructures. Yet few solutions are available for jointly optimizing caching and routing that provide performance guarantees for networks with arbitrary topology. We take a holistic approach towards this fundamental problem by analyzing its complexity in all the cases and developing polynomial-time algorithms with approximation guarantees in important special cases. We also reveal the fundamental challenge in achieving guaranteed approximation in the general case and propose an alternating optimization algorithm with good empirical performance and fast convergence. Our algorithms have demonstrated superior performance in both routing cost and congestion compared to the state-of-the-art solutions in evaluations based on real topology and request traces.

In-network caching and flexible routing are two of the most celebrated advantages of next generation network infrastructures. Yet few solutions are available for jointly optimizing caching and routing that provide performance guarantees for an arbitrary topology. We take a holistic approach towards this fundamental problem by analyzing its complexity in all the cases and developing polynomial-time algorithms with approximation guarantees in important special cases. We also reveal the fundamental challenge in achieving guaranteed approximation in the general case and propose an alternating optimization algorithm with good performance and fast convergence. Our algorithms have demonstrated superior performance in both routing cost and congestion compared to the state-of-the-art solutions in evaluations based on real topology and request traces.