Ma and Wong [IEEE TCAD '12] introduced and studied the Rectangle Escape problem, motivated by bus escape routing in printed circuit board design. In this problem, we are given an axis-parallel rectangle R, a set 𝒮 of axis-parallel rectangles fully contained in R, and an integer d. The goal is to determine whether each rectangle in 𝒮 can be extended in one of the four axis-parallel directions (up, down, left, or right) to the boundary of R such that no point is covered by more than d extended rectangles. We revisit Rectangle Escape and resolve several open complexity questions. Ahmadinejad et al. [TCS '17] studied Rectangle Escape and its variants where rectangles are only allowed to be extended in a subset of directions - most notably, in two directions, a variant they termed Bidirectional REP. They showed that the problem is NP-complete when extensions are limited to two adjacent directions and d = 3, but left open the complexity of the case when d = 2. Additionally, the case for two opposite directions remained unresolved for any d ≥ 2. We resolve the first question by showing that Bidirectional REP is NP-complete even when extensions are restricted to two adjacent directions and d = 2. We also settle the complexity of Rectangle Escape with two opposite directions by proving that the problem is NP-complete when d is part of the input but solvable in 𝒪(n log n) time for any constant d. Finally, we consider the special case where all extended rectangles must be disjoint, that is, d = 1. We show an unconditional lower bound of Ω(n log n) with a matching upper bound of 𝒪(n log n) for all variants. This improves upon a sequence of algorithms for the setting with all four directions allowed and d = 1, starting with an 𝒪(n⁶)-time algorithm, later improved to 𝒪(n⁴), and then to O(n³).

We revisit connectivity-constrained coverage through a unifying model, Partial Connected Red-Blue Dominating Set (PartialConRBDS). Given a bipartite graph G = (R∪ B,E) with red vertices R and blue vertices B, an auxiliary connectivity graph G_{conn} on R, and integers k,t, the task is to find a set S ⊆ R with |S| ≤ k such that G_{conn}[S] is connected and S dominates at least t blue vertices. This formulation captures connected variants of Maximum Coverage [Hochbaum-Rao, Inf. Proc. Lett., 2020; D'Angelo-Delfaraz, AAMAS 2025], Partial Vertex Cover, and Partial Dominating Set [Khuller et al., SODA 2014; Lamprou et al., TCS 2021] via standard encodings. Limits to parameterized tractability. PartialConRBDS is W[1]-hard parameterized by k even under strong restrictions: it remains hard when G_{conn} is a clique or a star and the incidence graph G is 3-degenerate, or when G is K_{2,2}-free. Inapproximability. For every ε > 0, there is no polynomial-time (1, 1-1/e+ε)-approximation unless 𝖯 = NP. Moreover, under ETH, no algorithm running in f(k)⋅ n^{o(k)} time achieves an g(k)-approximation for k for any computable function g(⋅), or for any ε > 0, a (1-1/e+ε)-approximation for t. Graphical special cases. Partial Connected Dominating Set is W[2]-hard parameterized by k and inherits the same ETH-based f(k)⋅ n^{o(k)} inapproximability bound as above; Partial Connected Vertex Cover is W[1]-hard parameterized by k. These hardness boundaries delineate a natural "sweet spot" for study: within appropriate structural restrictions on the incidence graph, one can still aim for fine-grained (FPT) approximations. Our algorithms. We solve PartialConRBDS exactly by reducing it to Relaxed Directed Steiner Out-Tree in time (2e)^t ⋅ n^{𝒪(1)}. For biclique-free incidences (i.e., when G excludes K_{d,d} as an induced subgraph), we obtain two complementary parameterized schemes: - An Efficient Parameterized Approximation Scheme (EPAS) running in time 2^{𝒪(k² d/ε)}⋅ n^{𝒪(1)} that either returns a connected solution of size at most k covering at least (1-ε)t blue vertices, or correctly reports that no connected size-k solution covers t; and - A Parameterized Approximation Scheme (PAS) running in time 2^{𝒪(kd(k²+log d))}⋅ n^{𝒪(1/ε)} that either returns a connected solution of size at most (1+ε)k covering at least t blue vertices, or correctly reports that no connected size-k solution covers t. Together, these results chart the boundary between hardness and FPT-approximability for connectivity-constrained coverage.

The pathwidth of a graph is a measure of how path-like the graph is. The Pathwidth One Vertex Deletion (POVD) problem asks whether, given an undirected graph G and an integer k, one can delete at most k vertices from G so that the remaining graph has pathwidth at most one. This is a natural variation of the classical Feedback vertex Set (FVS) problem, where the deletion of at most k vertices results in a graph of treewidth at most one. In this work, we investigate POVD in the realm of approximation algorithms. We first design a 3-approximation algorithm for POVD running in polynomial time. Then, using this constant factor approximation algorithm, we obtain a randomized parameterized approximation algorithm for POVD running in time 𝒪^*((h_β)^k), that improves the fastest existing running times for approximation ratios in the range (1.76147,3). Here the constant h_β depends on the approximation factor β alone and has value 2^{(3-β)}, which lies in the range (1,2.3596), when β ∈ (1.76147,3). Taking inspiration from two extensively studied problems, namely Connected FVS and Independent FVS, we investigate two variations of the POVD problem from the perspective of parameterized algorithms. These variations are the connected variant, called Connected pathwidth One Vertex Deletion (CPOVD) and the independent variant, called Independent Pathwidth One Vertex Deletion (IPOVD). While in CPOVD the subgraph G[S] induced by the vertices to be deleted needs to be connected, in IPOVD it needs to be independent. Specifically, we show the following results. - CPOVD can be solved in {𝒪}^*(14^k) time and admits no polynomial kernel unless NP ⊆ {co-NP/poly}. - IPOVD can be solved in {𝒪}^*(7^k) time, and admits a kernel of size 𝒪(k³).

In this paper, we study the Achromatic Number problem. Given a graph G and an integer k, the task is to determine whether there exists a proper coloring of G, using at least k colors, in which every pair of distinct colors appears on the endpoints of some edge. It was established early on that the problem is fixed-parameter tractable (FPT)- even before the formal development of parameterized complexity. In fact, Farber, Hahn, Hell, and Miller [JCTB, 1986] devised an algorithm with a running time of 𝒪(f(k) ⋅ |E(G)|). Although the exact form of f(k) was not specified, it appears to be at least doubly exponential in k. In our work, we first present an algorithm with an explicit dependence on k, and then introduce another algorithm that is parameterized by the vertex cover number of the graph. More formally, we show the following. - Achromatic Number is solvable in time 2^𝒪(k⁵)+𝒪(|E(G)|). - Achromatic Number admits a polynomial kernel when the input is restricted to a d-degenerate graph and a more efficient kernel on trees. - We also study the parameterized complexity of the problem with respect to Vertex Cover and show that it admits an FPT algorithm running in time 2^𝒪(𝓁²) ⋅ n^𝒪(1), where 𝓁 is the size of a vertex cover.

A module of a graph G is a set of vertices that have the same set of neighbours outside. Modules of a graphs form a so-called partitive family and thereby can be represented by a unique tree MD(G), called the modular decomposition tree. Motivated by the central role of modules in numerous algorithmic graph theory questions, the problem of efficiently computing MD(G) has been investigated since the early 70's. To date the best algorithms run in linear time but are all rather complicated. By combining previous algorithmic paradigms developed for the problem, we are able to present a simpler linear-time that relies on very simple data-structures, namely slice decomposition and sequences of rooted ordered trees.

Let G be a weighted graph embedded in a metric space (M, d_M). The vertices of G correspond to the points in M, with the weight of each edge uv being the distance d_M(u,v) between their respective points in M. The dilation (or stretch) of G is defined as the minimum factor t such that, for any pair of vertices u,v, the distance between u and v - represented by the weight of a shortest u,v-path - is at most t⋅ d_M(u,v). We study Dilation t-Augmentation, where the objective is, given a metric M, a graph G, and numerical values k and t, to determine whether G can be transformed into a graph with dilation t by adding at most k edges. Our primary focus is on the scenario where the metric M is the shortest path metric of an unweighted graph Γ. Even in this specific case, Dilation t-Augmentation remains computationally challenging. In particular, the problem is W[2]-hard parameterized by k when Γ is a complete graph, already for t = 2. Our main contribution lies in providing new insights into the impact of combinations of various parameters on the computational complexity of the problem. We establish the following. - The parameterized dichotomy of the problem with respect to dilation t, when the graph G is sparse: Parameterized by k, the problem is FPT for graphs excluding a biclique K_{d,d} as a subgraph for t ≤ 2 and the problem is W[1]-hard for t ≥ 3 even if G is a forest consisting of disjoint stars. - The problem is FPT parameterized by the combined parameter k+t+Δ, where Δ is the maximum degree of the graph G or Γ.

In this paper, we study the Eulerian Strong Component Arc Deletion problem, where the input is a directed multigraph and the goal is to delete the minimum number of arcs to ensure every strongly connected component of the resulting digraph is Eulerian. This problem is a natural extension of the Directed Feedback Arc Set problem and is also known to be motivated by certain scenarios arising in the study of housing markets. The complexity of the problem, when parameterized by solution size (i.e., size of the deletion set), has remained unresolved and has been highlighted in several papers. In this work, we answer this question by ruling out (subject to the usual complexity assumptions) a fixed-parameter algorithm (FPT algorithm) for this parameter and conduct a broad analysis of the problem with respect to other natural parameterizations. We prove both positive and negative results. Among these, we demonstrate that the problem is also hard (W[1]-hard or even para-NP-hard) when parameterized by either treewidth or maximum degree alone. Complementing our lower bounds, we establish that the problem is in XP when parameterized by treewidth and FPT when parameterized either by both treewidth and maximum degree or by both treewidth and solution size. We show that on simple digraphs, these algorithms have near-optimal asymptotic dependence on the treewidth assuming the Exponential Time Hypothesis.

Vertex (s, t)-Cut and Vertex Multiway Cut are two fundamental graph separation problems in algorithmic graph theory. We study matroidal generalizations of these problems, where in addition to the usual input, we are given a representation R ∈ 𝔽^{r × n} of a linear matroid ℳ = (V(G), ℐ) of rank r in the input, and the goal is to determine whether there exists a vertex subset S ⊆ V(G) that has the required cut properties, as well as is independent in the matroid ℳ. We refer to these problems as Independent Vertex (s, t){-cut}, and Independent Multiway Cut, respectively. We show that these problems are fixed-parameter tractable (FPT) when parameterized by the solution size (which can be assumed to be equal to the rank of the matroid ℳ). These results are obtained by exploiting the recent technique of flow augmentation [Kim et al. STOC '22], combined with a dynamic programming algorithm on flow-paths á la [Feige and Mahdian, STOC '06] that maintains a representative family of solutions w.r.t. the given matroid [Marx, TCS '06; Fomin et al., JACM]. As a corollary, we also obtain FPT algorithms for the independent version of Odd Cycle Transversal. Further, our results can be generalized to other variants of the problems, e.g., weighted versions, or edge-deletion versions.

In this paper, we study the Eulerian Strong Component Arc Deletion problem, where the input is a directed multigraph and the goal is to delete the minimum number of arcs to ensure every strongly connected component of the resulting digraph is Eulerian. This problem is a natural extension of the Directed Feedback Arc Set problem and is also known to be motivated by certain scenarios arising in the study of housing markets. The complexity of the problem, when parameterized by solution size (i.e., size of the deletion set), has remained unresolved and has been highlighted in several papers. In this work, we answer this question by ruling out (subject to the usual complexity assumptions) a fixed-parameter tractable (FPT) algorithm for this parameter and conduct a broad analysis of the problem with respect to other natural parameterizations. We prove both positive and negative results. Among these, we demonstrate that the problem is also hard (W[1]-hard or even para-NP-hard) when parameterized by either treewidth or maximum degree alone. Complementing our lower bounds, we establish that the problem is in XP when parameterized by treewidth and FPT when parameterized either by both treewidth and maximum degree or by both treewidth and solution size. We show that these algorithms have near-optimal asymptotic dependence on the treewidth assuming the Exponential Time Hypothesis.

For an undirected graph G, a pair of vertex disjoint subsets (A, B) is a pair of perfectly matched sets if each vertex in A (resp. B) has exactly one neighbor in B (resp. A). In the above, the size of the pair is |A| (= |B|). Given a graph G and a positive integer k, the Perfectly Matched Sets problem asks whether there exists a pair of perfectly matched sets of size at least k in G. This problem is known to be NP-hard on planar graphs and W[1]-hard on general graphs, when parameterized by k. However, little is known about the parameterized complexity of the problem in restricted graph classes. In this work, we study the problem parameterized by k, and design FPT algorithms for: i) apex-minor-free graphs running in time 2^O(√k)⋅ n^O(1), and ii) K_{b,b}-free graphs. We obtain a linear kernel for planar graphs and k^𝒪(d)-sized kernel for d-degenerate graphs. It is known that the problem is W[1]-hard on chordal graphs, in fact on split graphs, parameterized by k. We complement this hardness result by designing a polynomial-time algorithm for interval graphs.

A matching $M$ in a graph $G$ is said to be uniquely restricted if there is no other matching in $G$ that matches the same set of vertices as $M$. We describe a polynomial-time algorithm to compute a maximum cardinality uniquely restricted matching in an interval graph, thereby answering a question of Golumbic, Hirst, and Lewenstein [ Algorithmica, 31 (2001), pp. 139--154]. Our algorithm actually solves the more general problem of computing a maximum cardinality “weak independent set” in an interval nest digraph, which may be of independent interest. Further, we give linear-time algorithms for computing maximum cardinality uniquely restricted matchings in proper interval graphs and bipartite permutation graphs.