Search

The ArtGallery problem is a fundamental visibility problem in Computational Geometry. The input consists of a simple polygon P, (possibly infinite) sets G and C of points within P, and an integer k; the task is to decide if at most k guards can be placed on points in G so that every point in C is visible to at least one guard. In the classic formulation of ArtGallery, G and C consist of all the points within P. Other well-known variants restrict G and C to consist either of all the points on the boundary of P or of all the vertices of P. Recently, three new important discoveries were made: the above mentioned variants of ArtGallery are all W[1]-hard with respect to k [Bonnet and Miltzow in 24th Annual European Symposium on Algorithms (Aarhus 2016)], the classic variant has an O (log k) -approximation algorithm [Bonnet and Miltzow in 33rd International Symposium on Computational Geometry (Brisbane 2017)], and it may require irrational guards [Abrahamsen et al. in 33rd International Symposium on Computational Geometry (Brisbane 2017)]. Building upon the third result, the classic variant and the case where G consists only of all the points on the boundary of P were both shown to be ∃ R -complete [Abrahamsen et al. in 50th Annual ACM SIGACT Symposium on Theory of Computing (Los Angeles 2018)]. Even when both G and C consist only of all the points on the boundary of P, the problem is not known to be in NP. Given the first discovery, the following question was posed by Giannopoulos [Lorentz Workshop on Fixed-Parameter Computational Geometry (Leiden 2016)]: Is ArtGallery FPT with respect to r, the number of reflex vertices? In light of the developments above, we focus on the variant where G and C consist of all the vertices of P, called Vertex-Vertex Art Gallery. Apart from being a variant of ArtGallery, this case can also be viewed as the classic DominatingSet problem in the visibility graph of a polygon. In this article, we show that the answer to the question by Giannopoulos is positive: Vertex-VertexArtGallery is solvable in time r O (r 2) · n O (1) . Furthermore, our approach extends to assert that Vertex-BoundaryArtGallery and Boundary-VertexArtGallery are both FPT as well. To this end, we utilize structural properties of "almost convex polygons" to present a two-stage reduction from Vertex-VertexArtGallery to a new constraint satisfaction problem (whose solution is also provided in this paper) where constraints have arity 2 and involve monotone functions. [ABSTRACT FROM AUTHOR]

Fradkin and Seymour (J Comb Theory Ser B 110:19–46, 2015) defined the class of digraphs of bounded independence number as a generalization of the class of tournaments. They argued that the class of digraphs of bounded independence number is structured enough to be exploited algorithmically. In this paper, we further strengthen this belief by showing that several cut problems that admit sub-exponential time parameterized algorithms (a trait uncommon to parameterized algorithms) on tournaments, including Directed Feedback Arc Set, Directed Cutwidth and Optimal Linear Arrangement, also admit such algorithms on digraphs of bounded independence number. Towards this, we rely on the generic approach of Fomin and Pilipczuk (in: Proceedings of the Algorithms—ESA 2013—21st Annual European Symposium, Sophia Antipolis, France, September 2–4, 2013, pp. 505–516, 2013), where to get the desired algorithms, it is enough to bound the number of k-cuts in digraphs of bounded independence number by a sub-exponential FPT function (Fomin and Pilipczuk bounded the number of k-cuts in transitive tournaments). Specifically, our main technical contribution is a combinatorial result that proves that the yes-instances of the problems (defined above) have a sub-exponential number of k-cuts. We prove this bound by using a combination of chromatic coding, inductive reasoning and exploiting the structural properties of these digraphs. [ABSTRACT FROM AUTHOR]

We study the Steiner Tree problem on unit disk graphs. Given a n vertex unit disk graph G, a subset R ⊆ V (G) of t vertices and a positive integer k, the objective is to decide if there exists a tree T in G that spans over all vertices of R and uses at most k vertices from V \ R . The vertices of R are referred to as terminals and the vertices of V (G) \ R as Steiner vertices. First, we show that the problem is NP-hard. Next, we prove that the Steiner Tree problem on unit disk graphs can be solved in n O (t + k) time. We also show that the Steiner Tree problem on unit disk graphs parameterized by k has an FPT algorithm with running time 2 O (k) n O (1) . In fact, the algorithms are designed for a more general class of graphs, called clique-grid graphs Fomin (Discret. Comput. Geometry 62(4):879–911, 2019). We mention that the algorithmic results can be made to work for Steiner Tree problem on disk graphs with bounded aspect ratio. Finally, we prove that Steiner Tree problem on disk graphs parameterized by k, is W[1]-hard. [ABSTRACT FROM AUTHOR]

The class of assignment problems is a fundamental and well-studied class in the intersection of Social Choice, Computational Economics and Discrete Allocation. In a general assignment problem, a group of agents expresses preferences over a set of items, and the task is to allocate items to agents in an “optimal” way. A verification variant of this problem includes an allocation as part of the input, and the question becomes whether this allocation is “optimal”. In this paper, we generalize the verification variant to the setting where each agent is equipped with multiple incomplete preference lists: Each list (called a layer) is a ranking of items in a possibly different way according to a different criterion. In particular, we introduce three multi-layer verification problems, each corresponds to an optimality notion that weakens the notion of global optimality (that is, pareto optimality in multiple layers) in a different way. Informally, the first notion requires that, for each group of agents whose size is exactly some input parameter k, the agents in the group will not be able to trade their assigned items among themselves and benefit in at least α layers; the second notion is similar, but it concerns all groups of size at most k rather than exactly k; the third notion strengthens these notions by requiring that groups of k agents will not be part of possibly larger groups that benefit in at least α layers. We study the three problems from the perspective of parameterized complexity under several natural parameterizations such as the number of layers, the number of agents, the number of items, the number of allocated items, the maximum length of a preference list, and more. We present an almost comprehensive picture of the parameterized complexity of the problems with respect to these parameters. [ABSTRACT FROM AUTHOR]

The Terrain Guarding problem is a well-known variant of the famous Art Gallery problem. Only second to Art Gallery, it is the most well-studied visibility problem in Discrete and Computational Geometry, which has also attracted attention from the viewpoint of Parameterized complexity. In this paper, we focus on the parameterized complexity of Terrain Guarding (both discrete and continuous) with respect to two natural parameters. First we show that, when parameterized by the number r of reflex vertices in the input terrain, the problem has a polynomial kernel. We also show that, when parameterized by the number c of minima in the terrain, Discrete Orthogonal Terrain Guarding has an XP algorithm. [ABSTRACT FROM AUTHOR]

Among the twenty-five papers presented at IPEC, we invited the authors of the papers with the best scores of Program Committee to submit the full extended versions to this volume. We are pleased to present this special issue of Algorithmica dedicated to the 16th International Symposium on Parameterized and Exact Computation (IPEC 2021) which took place September 8-10, 2021. This special issue is a successor of the following special issue volumes of Algorithmica: Volumes 64(1)-2012 and 65(4)-2013 dedicated to IPEC 2010, held in Chennai (India); Volume 71(3)-2015 dedicated to IPEC 2013, held in Sophia Antipolis (France); Volume 75(2)-2016 dedicated to IPEC 2014, held in Wroclaw (Poland); Volume 79(1)-2017 dedicated to IPEC 2015, held in Patras (Greece); Volume 81(2)-2019 dedicated to IPEC 2016, held in Aarhus (Denmark); Volume 81(10)-2019 dedicated to IPEC 2017, held in Vienna (Austria); Volume 82(8)-2020 dedicated to IPEC 2018, held in Helsinki (Finland); Volume 83(8)-2021 dedicated to IPEC 2019, held in Munich (Germany); and Volume 84(8)-2022 dedicated to IPEC 2020, held online. [Extracted from the article]

Given an n-vertex digraph D and a non-negative integer k, the Minimum Directed Bisection problem asks if the vertices of D can be partitioned into two parts, say L and R, such that | L | and | R | differ by at most 1 and the number of arcs from R to L is at most k. This problem is known to be NP-hard even when k = 0 . We investigate the parameterized complexity of this problem on semicomplete digraphs. We show that Minimum Directed Bisection admits a sub-exponential time fixed-parameter tractable algorithm on semicomplete digraphs. We also show that Minimum Directed Bisection admits a polynomial kernel on semicomplete digraphs. To design the kernel, we use (n , k , k 2) -splitters, which, to the best of our knowledge, have never been used before in the design of kernels. We also prove that Minimum Directed Bisection is NP-hard on semicomplete digraphs, but polynomial time solvable on tournaments. [ABSTRACT FROM AUTHOR]

A tournament is a directed graph in which there is a single arc between every pair of distinct vertices. Given a tournament T on n vertices, we explore the classical and parameterized complexity of the problems of determining if T has a cycle packing (a set of pairwise arc-disjoint cycles) of size k and a triangle packing (a set of pairwise arc-disjoint triangles) of size k. We refer to these problems as Arc-disjoint Cycles in Tournaments (ACT) and Arc-disjoint Triangles in Tournaments (ATT), respectively. Although the maximization version of ACT can be seen as the dual of the well-studied problem of finding a minimum feedback arc set (a set of arcs whose deletion results in an acyclic graph) in tournaments, surprisingly no algorithmic results seem to exist for ACT. We first show that ACT and ATT are both NP-complete. Then, we show that the problem of determining if a tournament has a cycle packing and a feedback arc set of the same size is NP-complete. Next, we prove that ACT is fixed-parameter tractable via a 2 O (k log k) n O (1) -time algorithm and admits a kernel with O (k) vertices. Then, we show that ATT too has a kernel with O (k) vertices and can be solved in 2 O (k) n O (1) time. Afterwards, we describe polynomial-time algorithms for ACT and ATT when the input tournament has a feedback arc set that is a matching. We also prove that ACT and ATT cannot be solved in 2 o (n) n O (1) time under the exponential-time hypothesis. [ABSTRACT FROM AUTHOR]

Agrawal et al. (ACM Trans Comput Theory 10(4):18:1–18:25, 2018. https://doi.org/10.1145/3265027) studied a simultaneous variant of the classic Feedback Vertex Set problem, called Simultaneous Feedback Vertex Set (Sim-FVS). Here, we consider the edge variant of the problem, namely, Simultaneous Feedback Edge Set (Sim-FES). In this problem, the input is an n-vertex graph G, a positive integer k, and a coloring function col: E (G) → 2 [ α ] , and the objective is to check whether there is an edge subset S of cardinality k in G such that for each i ∈ [ α ] , G i - S is acyclic. Unlike the vertex variant of the problem, when α = 1 , the problem is equivalent to finding a maximal spanning forest and hence it is polynomial time solvable. We show that for α = 3 , Sim-FES is NP-hard, and does not admit an algorithm of running time 2 o (k) n O (1) unless ETH fails. This hardness result is complimented by an FPT algorithm for Sim-FES running in time 2 ω k α + α log k n O (1) where ω is the exponent in the running time of matrix multiplication. The same algorithm gives a polynomial time algorithm for the case when α = 2 . We also give a kernel for Sim-FES with (k α) O (α) vertices. Finally, we consider a "dual" version of the problem called Maximum Simultaneous Acyclic Subgraph and give an FPT algorithm with running time 2 ω q α n O (1) , where q is the number of edges in the output subgraph. [ABSTRACT FROM AUTHOR]

In a multiwinner election based on the Condorcet criterion, we are given a set of candidates, and a set of voters with strict preference rankings over the candidates. A committee is weakly Gehrlein stable (WGS) if each committee member is preferred to each non-member by at least half of the voters. Recently, Aziz et al. [IJCAI 2017] studied the computational complexity of finding a WGS committee of size k. They show that this problem is NP-hard in general and polynomial-time solvable when the number of voters is odd. In this article, we initiate a systematic study of the problem in the realm of parameterized complexity. We first show that the problem is W[1]-hard when parameterized by the size of the committee. To overcome this intractability result, we use a known reformulation of WGS as a problem on directed graphs and then use parameters that measure the “structure” of these directed graphs. We show that the problem is fixed parameter tractable and admits linear kernels with respect to these parameters; and also present an exact-exponential time algorithm with running in time O (1. 2207 n n O (1)) , where n denotes the number of candidates. [ABSTRACT FROM AUTHOR]

In this paper, we study the NP-complete colorful variant of the classic matching problem, namely, the Rainbow Matching problem. Given an edge-colored graph G and a positive integer k, the goal is to decide whether there exists a matching of size at least k such that the edges in the matching have distinct colors. Previously, in [MFCS'17], we studied this problem from the view point of Parameterized Complexity and gave efficient FPT algorithms as well as a quadratic kernel on paths. In this paper we design a quadratic vertex kernel for Rainbow Matching on general graphs; generalizing the earlier quadratic kernel on paths to general graphs. For our kernelization algorithm we combine a graph decomposition method with an application of expansion lemma. [ABSTRACT FROM AUTHOR]

Every connected graph on n vertices has a cut of size at least n − 1. We call this bound the spanning tree bound. In the Max-Cut Above Spanning Tree (Max-Cut-AST) problem, we are given a connected n-vertex graph G and a non-negative integer k, and the task is to decide whether G has a cut of size at least n − 1 + k. We show that Max-Cut-AST admits an algorithm that runs in time O (8 k n O (1)) , and hence it is fixed parameter tractable with respect to k. Furthermore, we show that Max-Cut-AST has a polynomial kernel of size O (k 5) . [ABSTRACT FROM AUTHOR]

We give algorithms with running time 2 O (k log k) · n O (1) for the following problems. Given an n-vertex unit disk graph G and an integer k, decide whether G contains a path on exactly/at least k vertices, a cycle on exactly k vertices, a cycle on at least k vertices, a feedback vertex set of size at most k, and a set of k pairwise vertex-disjoint cycles. For the first three problems, no subexponential time parameterized algorithms were previously known. For the remaining two problems, our algorithms significantly outperform the previously best known parameterized algorithms that run in time 2 O (k 0.75 log k) · n O (1) . Our algorithms are based on a new kind of tree decompositions of unit disk graphs where the separators can have size up to k O (1) and there exists a solution that crosses every separator at most O (k) times. The running times of our algorithms are optimal up to the log k factor in the exponent, assuming the exponential time hypothesis. [ABSTRACT FROM AUTHOR]

The notion of stability is the foundation of several classic problems in economics and computer science that arise in a wide-variety of real-world situations, including Stable Marriage, Stable Roommate, Hospital Resident and Group Activity Selection. We study this notion in the context of barter exchange markets. The input of our problem of interest consists of a set of people offering goods/services, with each person subjectively assigning values to a subset of goods/services offered by other people. The goal is to find a stable transaction, a set of cycles that is stable in the following sense: there does not exist a cycle such that every person participating in that cycle prefers to his current "status". For example, consider a market where families are seeking vacation rentals and offering their own homes for the same. Each family wishes to acquire a vacation home in exchange of its own home without any monetary exchange. We study such a market by analyzing a stable transaction of houses involving cycles of fixed length. The underlying rationale is that an entire trade/exchange fails if any of the participating agents cancels the agreement; as a result, shorter (trading) cycles are desirable. We show that given a transaction, it can be verified whether or not it is stable in polynomial time, and that the problem of finding a stable transaction is NP-hard even if each person desires only a small number of other goods/services. Having established these results, we study the problem of finding a stable transaction in the framework of parameterized algorithms. [ABSTRACT FROM AUTHOR]

In the Cycle Packing problem, we are given an undirected graph G, a positive integer r, and the task is to check whether there exist r vertex-disjoint cycles. In this paper, we study Cycle Packing with respect to a structural parameter, namely, distance to proper interval graphs (indifference graphs). In particular, we show that Cycle Packing is fixed-parameter tractable (FPT) when parameterized by t, the size of a proper interval deletion set. For this purpose, we design an algorithm with O (2 O (t log t) n O (1)) running time. Bodlaender et al. (Theor Comput Sci 511:117–136, 2013) studied several structural parameterizations for Cycle Packing and our FPT algorithm fills a gap in their ecology of parameterizations. We combine color coding, greedy strategy and dynamic programming based on structural properties of proper interval graphs in a non-trivial fashion to obtain the FPT algorithm. Our belief is that this approach is quite general and can be useful in solving many other problems with the same parameterization. [ABSTRACT FROM AUTHOR]

In the Partial Information Network Query (PINQ) problem, we are given a host graph H, and a pattern P whose topology is partially known. We seek a connected subgraph of H that resembles P . PINQ is a generalization of Subgraph Isomorphism, where the topology of P is known, and Graph Motif, where the topology of P is unknown. This generalization addresses the major challenge of analyzing biological networks in the absence of certain topological data. In this paper, we use a non-standard hybridization of algebraic and combinatorial tools to develop an exact parameterized algorithm as well as an FPT-approximation scheme for PINQ. [ABSTRACT FROM AUTHOR]

In this paper, we study the NP-complete colorful variant of the classical Matching problem, namely, the Rainbow Matching problem. Given an edge-colored graph G and a positive integer k, this problem asks whether there exists a matching of size at least k such that all the edges in the matching have distinct colors. We first develop a deterministic algorithm that solves Rainbow Matching on paths in time O ⋆ 1 + 5 2 k and polynomial space. This algorithm is based on a curious combination of the method of bounded search trees and a "divide-and-conquer-like" approach, where the branching process is guided by the maintenance of an auxiliary bipartite graph where one side captures "divided-and-conquered" pieces of the path. Our second result is a randomized algorithm that solves Rainbow Matching on general graphs in time O ⋆ (2 k) and polynomial-space. Here, we show how a result by Björklund et al. (J Comput Syst Sci 87:119–139, 2017) can be invoked as a black box, wrapped by a probability-based analysis tailored to our problem. We also complement our two main results by designing kernels for Rainbow Matching on general and bounded-degree graphs. [ABSTRACT FROM AUTHOR]

The classic K-CYCLE problem asks if a graph G, with vertex-set V(G), has a simple cycle containing all vertices of a given set K⊆V(G). In terms of colored graphs, it can be rephrased as follows: Given a graph G, a set K⊆V(G) and an injective coloring c:K→{1,2,...,|K|}, decide if G has a simple cycle containing each color in {1,2,...,|K|} exactly once. Another problem widely known since the introduction of color coding is COLORFUL CYCLE. Given a graph G and a coloring c:V(G)→{1,2,...,k} for some k∈N, it asks if G has a simple cycle of length k containing each color in {1,2,...,k} exactly once. We study a generalization of these problems: Given a graph G, a set K⊆V(G), a list-coloring L:K→2{1,2,...,k∗} for some k∗∈N and a parameter k∈N, LISTK-CYCLE asks if one can assign a color to each vertex in K so that G has a simple cycle (of arbitrary length) containing exactly k vertices from K with distinct colors. We design a randomized algorithm for LISTK-CYCLE running in time 2knO(1) on an n-vertex graph, matching the best known running times of algorithms for both K-CYCLE and COLORFUL CYCLE. Moreover, unless the Set Cover Conjecture is false, our algorithm is essentially optimal. We also study a variant of LISTK-CYCLE that generalizes the classic HAMILTONICITY problem, where one specifies the size of a solution. Our results integrate three related algebraic approaches, introduced by Björklund, Husfeldt and Taslaman (SODA'12), Björklund, Kaski and Kowalik (STACS'13), and Björklund (FOCS'10). [ABSTRACT FROM AUTHOR]

MAX-CUT is a well-known classical NP-hard problem. This problem asks whether the vertex-set of a given graph G=(V,E) can be partitioned into two disjoint subsets, A and B, such that there exist at least p edges with one endpoint in A and the other endpoint in B. It is well known that if p≤|E|/2, the answer is necessarily positive. A widely-studied variant of particular interest to parameterized complexity, called (k,n-k)-MAX-CUT, restricts the size of the subset A to be exactly k. For the (k,n-k)-MAX-CUT problem, we obtain an O∗(2p)-time algorithm, improving upon the previous best O∗(4p+o(p))-time algorithm, as well as the first polynomial kernel. Our algorithm relies on a delicate combination of methods and notions, including independent sets, depth-search trees, bounded search trees, dynamic programming and treewidth, while our kernel relies on examination of the closed neighborhood of the neighborhood of a certain independent set of the graph G. [ABSTRACT FROM AUTHOR]

In the DIRECTED FEEDBACK VERTEX SET (DFVS) problem, we are given a digraph D on n vertices and a positive integer k, and the objective is to check whether there exists a set of vertices S such that F = D − S is an acyclic digraph. In a recent paper, Mnich and van Leeuwen [STACS 2016 ] studied the kernelization complexity of DFVS with an additional restriction on F—namely that F must be an out-forest, an out-tree, or a (directed) pumpkin—with an objective of shedding some light on the kernelization complexity of the DFVS problem, a well known open problem in the area. The vertex deletion problems corresponding to obtaining an out-forest, an out-tree, or a (directed) pumpkin are OUT-FOREST/OUT-TREE/PUMPKIN VERTEX DELETION SET, respectively. They showed that OUT-FOREST/OUT-TREE/PUMPKIN VERTEX DELETION SET admit polynomial kernels. Another open problem regarding DFVS is that, does DFVS admit an algorithm with running time 2O(k)nO(1)? We complement the kernelization programme of Mnich and van Leeuwen by designing fast FPT algorithms for the above mentioned problems. In particular, we design an algorithm for OUT-FOREST VERTEX DELETION SET that runs in time O(2.732knO(1)) and algorithms for PUMPKIN/OUT-TREE VERTEX DELETION SET that runs in time O(2.562knO(1)). As a corollary of our FPT algorithms and the recent result of Fomin et al. [STOC 2016] which gives a relation between FPT algorithms and exact algorithms, we get exact algorithms for OUT-FOREST/OUT-TREE/PUMPKIN VERTEX DELETION SET that run in time O(1.633nnO(1)), O(1.609nnO(1)) and O(1.609nnO(1)), respectively. [ABSTRACT FROM AUTHOR]

We study a broad class of graph partitioning problems. Each problem is defined by two constants, α and α . The input is a graph G, an integer k and a number p, and the objective is to find a subset $U\subseteq V$ of size k, such that α m + α m is at most (or at least) p, where m , m are the cardinalities of the edge sets having both endpoints, and exactly one endpoint, in U, respectively. This class of fixed-cardinality graph partitioning problems (FGPPs) encompasses Max ( k, n − k)- Cut, Min k- Vertex Cover, k- Densest Subgraph, and k- Sparsest Subgraph. Our main result is a 4Δ⋅ n time algorithm for any problem in this class, where Δ ≥ 1 is the maximum degree in the input graph. This resolves an open question posed by Bonnet et al. (Proc. International Symposium on Parameterized and Exact Computation, 2013). We obtain faster algorithms for certain subclasses of FGPPs, parameterized by p, or by ( k + p). In particular, we give a 4⋅ n time algorithm for Max ( k, n − k)- Cut, thus improving significantly the best known p ⋅ n time algorithm by Bonnet et al. [ABSTRACT FROM AUTHOR]

In this paper, we employ the multilinear detection technique, combined with proper colorings of graphs, to develop algorithms for two problems in bounded degree graphs. We focus mostly on the k-Internal Out-Branching ( k-IOB) problem, which asks if a given directed graph has an out-branching (i.e., a spanning tree with exactly one node of in-degree 0) with at least k internal nodes. The second problem, k-Tree, asks if a given undirected graph G has a (not necessarily induced) copy of a given tree T. That is, k-Tree asks whether T is a subgraph of G. We present an $$O^*(4^k)$$ time randomized algorithm for k-IOB, which improves the $$O^*$$ running time of the previous best known algorithm for this problem. Then, for directed graphs whose underlying (simple, undirected) graphs have bounded degree $$\varDelta $$ , we modify our algorithm to solve k-IOB in time $$O^*(2^{(2-\frac{\varDelta +1}{\varDelta (\varDelta -1)})k})$$ . For k- Tree in graphs of bounded degree 3, we obtain an $$O^*(1.914^k)$$ time randomized algorithm. In particular, all of our algorithms use polynomial space. [ABSTRACT FROM AUTHOR]

The problem of packing of equal disks (or circles) into a rectangle is a fundamental geometric problem. (By a packing here we mean an arrangement of disks in a rectangle without overlapping.) We consider the following algorithmic generalization of the equal disk packing problem. In this problem, for a given packing of equal disks into a rectangle, the question is whether by changing positions of a small number of disks, we can allocate space for packing more disks. More formally, in the repacking problem, for a given set of n equal disks packed into a rectangle and integers k and h, we ask whether it is possible by changing positions of at most h disks to pack n+k\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$n+k$$\end{document} disks. Thus the problem of packing equal disks is the special case of our problem with n=h=0\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$n=h=0$$\end{document}. While the computational complexity of packing equal disks into a rectangle remains open, we prove that the repacking problem is NP-hard already for h=0\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$h=0$$\end{document}. Our main algorithmic contribution is an algorithm that solves the repacking problem in time (h+k)O(h+k)·|I|O(1)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$(h+k)^{\mathcal {O}(h+k)}\cdot |I|^{\mathcal {O}(1)}$$\end{document}, where |I| is the input size. That is, the problem is fixed-parameter tractable parameterized by k and h. [ABSTRACT FROM AUTHOR]