Manuel Cáceres

Manuel Cáceres

Postdoctoral Researcher

University of Helsinki

Biography

I am an HIIT Postdoctoral Fellow at Aalto University working in the group Combinatorics of Efficient Computations led by Parinya Chalermsook. Before that I was a Postdoctoral Researcher at University of Helsinki working in the Graph Algorithms team led by Alexandru I. Tomescu. Previously, I was a Doctoral Student in the same group. My Doctoral Thesis is titled “Parameterized and Safe & Complete Graph Algorithms for Bioinformatics”. Before that, I was a Master Student from the Department of Computer Science at University of Chile. I worked under the supervision of Gonzalo Navarro. My thesis is titled “Compressed Suffix Trees for Repetitive Collections based on Block Trees”.

Interests

  • Algorithmic Bioinformatics
  • Graph Algorithms
  • String Algorithms
  • Compressed Data Structures
  • Safe & Complete Algorithms
  • Parameterized Algorithms

Education

  • PhD. in Computer Science, 2023

    University of Helsinki

  • MSc. in Computer Science, 2019

    University of Chile

  • Computer Science Engineering, Minor in Algorithms and Combinatorial Optimization, 2019

    University of Chile

  • BSc. in Computer Science, 2016

    University of Chile

Recent Publications

Width Helps and Hinders Splitting Flows

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.

Sorting Finite Automata via Partition Refinement

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.

Minimum Path Cover: The Power of Parameterization

We present the first publicly available high-performance implementation of state-of-the-art MPC algorithms, including the parameterized approaches. Our experiments on random DAGs show that parameterized algorithms are orders-of-magnitude faster on dense graphs. Additionally, we present new pre-processing heuristics based on transitive edge sparsification. We show that our heuristics improve MPC-solvers by orders-of-magnitude.

Minimum Chain Cover in Almost Linear Time

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})$.

Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond

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$.