Two-layer drawings of bipartite graphs place the vertices of each part on one of two parallel lines and draw the edges as straight-line links. Traditionally, the optimization goal is to find vertex permutations on one or both layers that minimize the induced number of edge crossings. This problem is NP-hard, and crossing-minimal solutions may still contain many crossings. Recently, there has been growing interest in an orthogonal optimization goal, namely removing all crossings by vertex splitting, i.e., replacing original vertices by two or more copies and distributing the adjacencies among them. In this paper, we study a natural extension of the two-layer vertex splitting problem in which the vertex order on one layer is constrained by a given auxiliary tree $T$, motivated by applications such as the visualization of anatomical hierarchies in the Human Reference Atlas. We investigate the parameterized complexity of this problem and obtain two main contributions: (1) a fixed-parameter algorithm with respect to the number $k$ of splits, and (2) an ETH-tight single-exponential fixed-parameter algorithm with respect to the maximum degree of $T$. Moreover, we build on the latter result to obtain an ETH-tight single-exponential algorithm for the classical unconstrained version of the problem, improving upon the previous $O^*(2^{k\cdot \log k})$ algorithms. Finally, we also implement our algorithm and show that it performs well in practice.
Alexander Firbas, R. Ganian, Sylvain Meunier et al.· 0 citations
We study the computation of minimum spanning trees subject to local degree constraints. Recent work (ICALP 2026) established that three natural formalizations of this problem share the exact same parameterized complexity under standard structural graph parameters, including treewidth, pathwidth and clique-width. This applies to the cases where every vertex has a single target degree (Specified Degree MST), or a degree upper bound (Bounded Degree MST), or is equipped with a set of admissible degrees (Set of Degrees MST). In this paper, we investigate these problems under more restrictive parameterizations and reveal that their complexity landscapes fundamentally diverge on bounded-treedepth graphs. Specifically, we prove that the former two problems are fixed-parameter tractable when parameterized by the treedepth of the input graph. In sharp contrast, we show that Set of Degrees MST remains W[1]-hard parameterized by treedepth, even when combined with the feedback vertex number (i.e., deletion distance to treewidth $1$). Finally, we show that this divergence seems to be specific to treedepth: we exclude an analogous W[1]-hardness result for Set of Degrees MST w.r.t. the vertex cover number and also rule out fixed-parameter algorithms for the former two problems w.r.t. deletion distance to constant pathwidth.
Narek Bojikian, Alexander Firbas, R. Ganian et al.· 0 citations
Instance selection is a vital technique for mitigating the computational bottlenecks of nearest-neighbor classification in large-scale supervised clustering. A classical theoretical formulation of this objective is the Minimum Consistent Subset (MCS) problem. While recent research has explored its complexity on unweighted graphs to uncover structural boundaries of tractability, arbitrary metric spaces are much more accurately modeled by (edge-)weighted graphs. In this paper, we develop a comprehensive fine-grained complexity map of MCS on both unweighted and weighted graphs. As our main result, we introduce a $3^{c \cdot(\mathrm{tw}+1)}\cdot n^{\mathrm{tw}+\mathcal{O}(1)}$ algorithm for $n$-vertex $c$-colored MCS instances on weighted graphs of treewidth $\mathrm{tw}$, substantially improving upon the previous state-of-the-art algorithm for unweighted MCS on trees both in terms of generality and running time. We complement this positive result with a series of lower bounds that rule out asymptotic improvements to the running time for both weighted and unweighted graphs under the Exponential Time Hypothesis (ETH). Moreover, we improve the recent slightly superexponential vertex-cover based algorithm for unweighted MCS (AAAI 2026) to a single-exponential one, and rule out further improvements to subexponential running times under the ETH. Together, our results strictly delineate the algorithmic boundaries of consistent subset selection across diverse metric structures.
R. Ganian, M. Vasilakis, Simon Wietheger· 0 citations