Stefan Kratsch

Stefan Kratsch

A large number of NP-hard graph problems can be solved in $f(w)n^{O(1)}$ time and space when the input graph is provided together with a tree decomposition of width $w$, in many cases with a modest exponential dependence $f(w)$ on $w$. Moreover, assuming the Strong Exponential-Time Hypothesis (SETH) we have essentially matching lower bounds for many such problems. They main drawback of these results is that the corresponding dynamic programming algorithms use exponential space, which makes them infeasible for larger $w$, and there is some evidence that this cannot be avoided. This motivates using somewhat more restrictive structure/decompositions of the graph to also get good (exponential) dependence on the corresponding parameter but use only polynomial space. A number of papers have contributed to this quest by studying problems relative to treedepth, and have obtained fast polynomial space algorithms, often matching the dependence on treewidth in the time bound. E.g., a number of connectivity problems could be solved by adapting the cut-and-count technique of Cygan et al. (FOCS 2011, TALG 2022) to treedepth, but this excluded well-known path and cycle problems such as Hamiltonian Cycle (Hegerfeld and Kratsch, STACS 2020). Recently, Nederlof et al. (SIDMA 2023) showed how to solve Hamiltonian Cycle, and several related problems, in $5^τn^{O(1)}$ randomized time and polynomial space when provided with an elimination forest of depth $τ$. We present a faster (also randomized) algorithm, running in $4^τn^{O(1)}$ time and polynomial space, for the same set of problems. We use ordered pairs of what we call consistent matchings, rather than perfect matchings in an auxiliary graph, to get the improved time bound.

Benjamin Bergougnoux, Vera Chekan, Stefan Kratsch

In this work we contribute to the study of the fine-grained complexity of problems parameterized by multi-clique-width, which was initiated by Fürer [ITCS 2017] and pursued further by Chekan and Kratsch [MFCS 2023]. Multi-clique-width is a parameter defined analogously to clique-width but every vertex is allowed to hold multiple labels simultaneously. This parameter is upper-bounded by both clique-width and treewidth (plus a constant), hence it generalizes both of them without an exponential blow-up. Conversely, graphs of multi-clique-width $k$ have clique-width at most $2^k$, and there exist graphs with clique-width at least $2^{Ω(k)}$. Thus, while the two parameters are functionally equivalent, the fine-grained complexity of problems may differ relative to them. As our first and main result we show that under ETH the Max Cut problem cannot be solved in time $n^{2^{o(k)}} \cdot f(k)$ on graphs of multi-clique-width $k$ for any computable function $f$. For clique-width $k$ an $n^{\mathcal{O}(k)}$ algorithm by Fomin et al. [SIAM J. Comput. 2014] is tight under ETH. This makes Max Cut the first known problem for which the tight running times differ for parameterization by clique-width and multi-clique-width and it contributes to the short list of known lower bounds of form $n^{2^{o(k)}} \cdot f(k)$. As our second contribution we show that Hamiltonian Cycle and Edge Dominating Set can be solved in time $n^{\mathcal{O}(k)}$ on graphs of multi-clique-width $k$ matching the tight running time for clique-width. These results answer three questions left open by Chekan and Kratsch [MFCS 2023].

Stefan Kratsch, Tomáš Masařík, Irene Muzi et al.

Given two disjoint sets $W_1$ and $W_2$ of points in the plane, the Optimal Discretization problem asks for the minimum size of a family of horizontal and vertical lines that separate $W_1$ from $W_2$, that is, in every region into which the lines partition the plane there are either only points of $W_1$, or only points of $W_2$, or the region is empty. Equivalently, Optimal Discretization can be phrased as a task of discretizing continuous variables: we would like to discretize the range of $x$-coordinates and the range of $y$-coordinates into as few segments as possible, maintaining that no pair of points from $W_1 \times W_2$ are projected onto the same pair of segments under this discretization. We provide a fixed-parameter algorithm for the problem, parameterized by the number of lines in the solution. Our algorithm works in time $2^{O(k^2 \log k)} n^{O(1)}$, where $k$ is the bound on the number of lines to find and $n$ is the number of points in the input. Our result answers in positive a question of Bonnet, Giannopolous, and Lampis [IPEC 2017] and of Froese (PhD thesis, 2018) and is in contrast with the known intractability of two closely related generalizations: the Rectangle Stabbing problem and the generalization in which the selected lines are not required to be axis-parallel.