Manuel Cáceres

Postdoctoral Researcher

Aalto University

manuel.caceres AT aalto.fi

Welcome

I am an HIIT Postdoctoral Fellow at Aalto University working with Professor Sándor Kisfaludi-Bak. My research interests are broadly in the area of efficient algorithms and data structures for problems on graphs and strings. I am particularly interested in understanding and overcoming intractable problems inside P, but in general I enjoy developing efficient solutions for intractable problems as well as understanding the limits of modern algorithmic techniques.

Interests

Graph Algorithms
String Algorithms
Paramaterized Algorithms
Algorithmic Bioinformatics
Compressed Data Structures
Approximation Algorithms

Education

PhD. in Computer Science, 2023

University of Helsinki
MSc. in Computer Science, 2019

University of Chile
Computer Engineering, 2019

University of Chile
BSc. in Computer Science, 2016

University of Chile

Featured Publications

Maximum Coverage k-Antichains and Chains: A Greedy Approach

Preprint

Maximum Coverage k-Antichains and Chains: A Greedy Approach

We obtain fast algorithms for maximum coverage $k$-antichains and chains, and show the limits of the $\texttt{greedy}$ heuristic in these contexts.

Feb 7, 2025

Practical Minimum Path Cover

Conference Publication

Practical Minimum Path Cover

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.

Jun 1, 2024

Width Helps and Hinders Splitting Flows

Journal Publication

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.

Jan 1, 2024

Sorting Finite Automata via Partition Refinement

Conference Publication

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.

Sep 4, 2023

Minimum Chain Cover in Almost Linear Time

Conference Publication

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

Jul 10, 2023

Parameterized Algorithms for String Matching to DAGs: Funnels and Beyond

Conference Publication

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

Jun 26, 2023

Recent Publications

Francisco Sena, Aleksandr Politov, Corentin Moumard, Manuel Cáceres, Sebastian Schmidt, Juha Harviainen, Alexandru I. Tomescu (2025). Identifying all snarls and superbubbles in linear-time, via a unified SPQR-tree framework. In arXiv.

PDF Code

Nicola Rizzo, Manuel Cáceres, Veli Mäkinen (2025). Practical colinear chaining on sequences revisited. In ISBRA 2025.

PDF Code DOI

Nicola Rizzo, Manuel Cáceres, Veli Mäkinen (2025). Exploiting uniqueness: seed-chain-extend alignment on elastic founder graphs. In ISMB 2025.

Code DOI

Manuel Cáceres, Andreas Grigorjew, Wanchote Po Jiamjitrak, Alexandru I. Tomescu (2025). Maximum Coverage k-Antichains and Chains: A Greedy Approach. In arXiv.

PDF

Manuel Cáceres, Brendan Mumey, Santeri Toivonen, Alexandru I. Tomescu (2024). Practical Minimum Path Cover. In SEA 2024.

Code DOI

See all publications