Polynomially-solvable problems on huge graphs are "practically tractable" only if their complexity is sufficiently low. Likewise, NP-hard problems admitting specialized solvers are "practically tractable" only on small-enough inputs. We plan to enlarge these two limits of "practical tractability", motivated by two key applications in Bioinformatics. Pangenomic graphs represent all the genetic variation in a population. On these, we will develop fixed-parameter tractable linear-time algorithms, whose complexity is linear in the size of the input, and possibly super-linear in the size of a small parameter of input. In transcriptomics we need to solve NP-hard problems about network flows. Here we will use safe subpaths to simplify the input to these problems. Our expected results will significantly speed up existing Bioinformatics methods, and scale them to inputs that were not feasible before. We expect them to be adopted also for other graph problems in Computer Science at large.

2024

2026