Source author record

Tuukka Korhonen

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Discrete Mathematics

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Finding Optimal Triangulations Parameterized by Edge Clique Cover

We consider problems that can be formulated as a task of finding an optimal triangulation of a graph w.r.t. some notion of optimality. We present algorithms parameterized by the size of a minimum edge clique cover ( $cc$ ) to such problems. This parameterization occurs naturally in many problems in this setting, e.g., in the perfect phylogeny problem $cc$ is at most the number of taxa, in fractional hypertreewidth $cc$ is at most the number of hyperedges, and in treewidth of Bayesian networks $cc$ is at most the number of non-root nodes. We show that the number of minimal separators of graphs is at most $2^{cc}$ , the number of potential maximal cliques is at most $3^{cc}$ , and these objects can be listed in times $O^*(2^{cc})$ and $O^*(3^{cc})$ , respectively, even when no edge clique cover is given as input; the $O^*(\cdot)$ notation omits factors polynomial in the input size. These enumeration algorithms imply $O^*(3^{cc})$ time algorithms for problems such as treewidth, weighted minimum fill-in, and feedback vertex set. For generalized and fractional hypertreewidth we give $O^*(4^m)$ time and $O^*(3^m)$ time algorithms, respectively, where $m$ is the number of hyperedges. When an edge clique cover of size $cc'$ is given as a part of the input we give $O^*(2^{cc'})$ time algorithms for treewidth, minimum fill-in, and chordal sandwich. This implies an $O^*(2^n)$ time algorithm for perfect phylogeny, where $n$ is the number of taxa. We also give polynomial space algorithms with time complexities $O^*(9^{cc'})$ and $O^*(9^{cc + O(\log^2 cc)})$ for problems in this framework.

preprint2022arXiv

Fixed-Parameter Tractability of Maximum Colored Path and Beyond

We introduce a general method for obtaining fixed-parameter algorithms for problems about finding paths in undirected graphs, where the length of the path could be unbounded in the parameter. The first application of our method is as follows. We give a randomized algorithm, that given a colored $n$ -vertex undirected graph, vertices $s$ and $t$ , and an integer $k$ , finds an $(s,t)$ -path containing at least $k$ different colors in time $2^k n^{O(1)}$ . This is the first FPT algorithm for this problem, and it generalizes the algorithm of Björklund, Husfeldt, and Taslaman [SODA 2012] on finding a path through $k$ specified vertices. It also implies the first $2^k n^{O(1)}$ time algorithm for finding an $(s,t)$ -path of length at least $k$ . Our method yields FPT algorithms for even more general problems. For example, we consider the problem where the input consists of an $n$ -vertex undirected graph $G$ , a matroid $M$ whose elements correspond to the vertices of $G$ and which is represented over a finite field of order $q$ , a positive integer weight function on the vertices of $G$ , two sets of vertices $S,T \subseteq V(G)$ , and integers $p,k,w$ , and the task is to find $p$ vertex-disjoint paths from $S$ to $T$ so that the union of the vertices of these paths contains an independent set of $M$ of cardinality $k$ and weight $w$ , while minimizing the sum of the lengths of the paths. We give a $2^{p+O(k^2 \log (q+k))} n^{O(1)} w$ time randomized algorithm for this problem.

preprint2021arXiv

Lower Bounds on Dynamic Programming for Maximum Weight Independent Set

We prove lower bounds on pure dynamic programming algorithms for maximum weight independent set (MWIS). We model such algorithms as tropical circuits, i.e., circuits that compute with $\max$ and $+$ operations. For a graph $G$ , an MWIS-circuit of $G$ is a tropical circuit whose inputs correspond to vertices of $G$ and which computes the weight of a maximum weight independent set of $G$ for any assignment of weights to the inputs. We show that if $G$ has treewidth $w$ and maximum degree $d$ , then any MWIS-circuit of $G$ has $2^{Ω(w/d)}$ gates and that if $G$ is planar, or more generally $H$ -minor-free for any fixed graph $H$ , then any MWIS-circuit of $G$ has $2^{Ω(w)}$ gates. An MWIS-formula is an MWIS-circuit where each gate has fan-out at most one. We show that if $G$ has treedepth $t$ and maximum degree $d$ , then any MWIS-formula of $G$ has $2^{Ω(t/d)}$ gates. It follows that treewidth characterizes optimal MWIS-circuits up to polynomials for all bounded degree graphs and $H$ -minor-free graphs, and treedepth characterizes optimal MWIS-formulas up to polynomials for all bounded degree graphs.

preprint2020arXiv

SMS in PACE 2020

We describe SMS, our submission to the exact treedepth track of PACE 2020. SMS computes the treedepth of a graph by branching on the small minimal separators of the graph.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.