Karol Węgrzycki
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Karol Węgrzycki has a total of 41 co-authors. Here are the top co-authors by number of shared publications:
- Jesper Nederlof
Utrecht University, The Netherlands
10 shared publications Piotr Sankowski
University of Warsaw, Warsaw, Poland
6 shared publicationsPiotr Wygocki
University of Warsaw, Warsaw, Poland
6 shared publications- Andrzej Pacuk
University of Warsaw, Warsaw, Poland
4 shared publications - Celine M. F. Swennenhuis
Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven, The Netherlands
4 shared publications - Michał Pilipczuk
University of Warsaw, Warsaw, Poland
4 shared publications
Latest Publications
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 2094-2105
Tight (S)ETH-Based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-machine Scheduling
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 2094-2105
Open AccessTight (S)ETH-Based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-machine Scheduling
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1314-1325
Beating Meet-in-the-Middle for Subset Balancing Problems
We consider exact algorithms for Subset Balancing, a family of related problems that generalizes Subset Sum, Partition, and Equal Subset Sum. Specifically, given as input an integer vector x→ ∈ ℤn and a constant-size coefficient set C ⊂ ℤ, we seek a nonzero solution vector c→ ∈ Cn satisfying c→ · x→ = 0. For C = {−d,…,d}, d > 1 and C = {−d,…,d}∖{0}, d > 2, we present algorithms that run in time O(|C|(0.5 − є)n) for a constant є > 0 that depends only on C. This improves on the result of Chen, Jin, Randolph and Servedio (SODA 2022), who broke the Meet-in-the-Middle barrier on these coefficient sets in the average-case setting. We also improve the best exact algorithm for Equal Subset Sum (Subset Balancing with C = {−1,0,1}), due to Mucha, Nederlof, Pawlewicz, and Węgrzycki (ESA 2019), by an exponential margin. This positively answers an open question of Jin, Williams, and Zhang (ESA 2025). Our results leave two natural cases in which we cannot yet break the Meet-in-the-Middle barrier: C = {−2, −1, 1, 2} and C = {−1, 1} (Partition). Our results bring the representation technique of Howgrave-Graham and Joux (CRYPTO 2010) from average-case to worst-case inputs for many C. This requires a variety of new techniques: we present strategies for (1) achieving good “mixing” with worst-case inputs, (2) creating flexible input representations for coefficient sets without 0, and (3) quickly recovering compatible solution pairs from sets of vectors containing “pseudosolution pairs”.
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1314-1325
Open AccessBeating Meet-in-the-Middle for Subset Balancing Problems
We consider exact algorithms for Subset Balancing, a family of related problems that generalizes Subset Sum, Partition, and Equal Subset Sum. Specifically, given as input an integer vector x→ ∈ ℤn and a constant-size coefficient set C ⊂ ℤ, we seek a nonzero solution vector c→ ∈ Cn satisfying c→ · x→ = 0. For C = {−d,…,d}, d > 1 and C = {−d,…,d}∖{0}, d > 2, we present algorithms that run in time O(|C|(0.5 − є)n) for a constant є > 0 that depends only on C. This improves on the result of Chen, Jin, Randolph and Servedio (SODA 2022), who broke the Meet-in-the-Middle barrier on these coefficient sets in the average-case setting. We also improve the best exact algorithm for Equal Subset Sum (Subset Balancing with C = {−1,0,1}), due to Mucha, Nederlof, Pawlewicz, and Węgrzycki (ESA 2019), by an exponential margin. This positively answers an open question of Jin, Williams, and Zhang (ESA 2025). Our results leave two natural cases in which we cannot yet break the Meet-in-the-Middle barrier: C = {−2, −1, 1, 2} and C = {−1, 1} (Partition). Our results bring the representation technique of Howgrave-Graham and Joux (CRYPTO 2010) from average-case to worst-case inputs for many C. This requires a variety of new techniques: we present strategies for (1) achieving good “mixing” with worst-case inputs, (2) creating flexible input representations for coefficient sets without 0, and (3) quickly recovering compatible solution pairs from sets of vectors containing “pseudosolution pairs”.
- Open Access
- 3 January 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
A Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints
In a classical scheduling problem, we are given a set of \(n\) jobs of unit length with precedence constraints, and the goal is to find a schedule of these jobs on \(m\) identical machines that minimizes the makespan. In standard 3-field notation, it is denoted as \(Pm|\text{prec},p_{j}=1|C_{\max}\) . For \(m=2\) machines, the problem can be solved in polynomial time. Settling the complexity for any constant \(m\geq 3\) is a longstanding open question in the field, asked by Lenstra and Rinnooy Kan [OR 1978] in the late 70s and prominently featured in the textbook of Garey and Johnson. Since then, the problem has been thoroughly investigated, but nontrivial solutions had been found only in special cases or relaxed settings. For example, despite the possibility of the problem being polynomially solvable in the exact setting, just the existence of an approximation-scheme is widely regarded as a major open problem (see the survey of Bansal [MAPS 2017]), but so far, only superpolynomial approximations are known. In this paper, we make the first progress on the exact complexity of \(Pm|\text{prec},p_{j}=1|C_{\max}\) . We present an algorithm that runs in \(2^{\mathcal{O}(\sqrt{n}\log{n})}\) time for \(m=\mathcal{O}(1)\) . Before our work, only a \(2^{\mathcal{O}(n)}\) time exact algorithm was known by Held and Karp [ACM 1961]. We introduce a notion of proper decomposition of the schedule. With this decomposition in hand, our approach can be presented in three parts. In the branch part, we branch on possible subschedules generated by proper decomposition. In the reconstruct part, we compute the schedule based on the partial answer. Interestingly, despite the fact that the depth of the branching may be linear, by memoization we can show that the total number of different subproblems is bounded by \(2^{\mathcal{O}(\sqrt{n}\log{n})}\) .- 3 January 2026
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
Open AccessA Subexponential Time Algorithm for Makespan Scheduling of Unit Jobs with Precedence Constraints
In a classical scheduling problem, we are given a set of \(n\) jobs of unit length with precedence constraints, and the goal is to find a schedule of these jobs on \(m\) identical machines that minimizes the makespan. In standard 3-field notation, it is denoted as \(Pm|\text{prec},p_{j}=1|C_{\max}\) . For \(m=2\) machines, the problem can be solved in polynomial time. Settling the complexity for any constant \(m\geq 3\) is a longstanding open question in the field, asked by Lenstra and Rinnooy Kan [OR 1978] in the late 70s and prominently featured in the textbook of Garey and Johnson. Since then, the problem has been thoroughly investigated, but nontrivial solutions had been found only in special cases or relaxed settings. For example, despite the possibility of the problem being polynomially solvable in the exact setting, just the existence of an approximation-scheme is widely regarded as a major open problem (see the survey of Bansal [MAPS 2017]), but so far, only superpolynomial approximations are known. In this paper, we make the first progress on the exact complexity of \(Pm|\text{prec},p_{j}=1|C_{\max}\) . We present an algorithm that runs in \(2^{\mathcal{O}(\sqrt{n}\log{n})}\) time for \(m=\mathcal{O}(1)\) . Before our work, only a \(2^{\mathcal{O}(n)}\) time exact algorithm was known by Held and Karp [ACM 1961]. We introduce a notion of proper decomposition of the schedule. With this decomposition in hand, our approach can be presented in three parts. In the branch part, we branch on possible subschedules generated by proper decomposition. In the reconstruct part, we compute the schedule based on the partial answer. Interestingly, despite the fact that the depth of the branching may be linear, by memoization we can show that the total number of different subproblems is bounded by \(2^{\mathcal{O}(\sqrt{n}\log{n})}\) . - Open Access
- 24 November 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (6) , 1-48
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
We revisit the classic task of finding the shortest tour of n points in d -dimensional Euclidean space, for any fixed constant d ⩾ 2. We determine the optimal dependence on ɛ in the running time of an algorithm that computes a (1 + ɛ)-approximate tour, under a plausible assumption. Specifically, we give an algorithm that runs in \(2^{\mathcal {O}(1/\varepsilon ^{d-1})} n\log n\) time. This improves the previously smallest dependence on ɛ in the running time \((1/\varepsilon)^{\mathcal {O}(1/\varepsilon ^{d-1})}n \log n\) of the algorithm by Rao and Smith (STOC 1998). We also show that a \(2^{o(1/\varepsilon ^{d-1})}\mathrm{poly}(n)\) algorithm would violate the Gap-Exponential Time Hypothesis (Gap-ETH). Our new algorithm builds upon the celebrated quadtree-based methods initially proposed by Arora (J. ACM 1998), but it adds a new idea that we call sparsity-sensitive patching . On a high level this lets the granularity with which we simplify the tour depend on how sparse it is locally. We demonstrate that our technique extends to other problems, by showing that for Steiner Tree and Rectilinear Steiner Tree it yields the same running time. We complement our results with a matching Gap-ETH lower bound for Rectilinear Steiner Tree.- 24 November 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (6) , 1-48
Open AccessA Gap-ETH-Tight Approximation Scheme for Euclidean TSP
We revisit the classic task of finding the shortest tour of n points in d -dimensional Euclidean space, for any fixed constant d ⩾ 2. We determine the optimal dependence on ɛ in the running time of an algorithm that computes a (1 + ɛ)-approximate tour, under a plausible assumption. Specifically, we give an algorithm that runs in \(2^{\mathcal {O}(1/\varepsilon ^{d-1})} n\log n\) time. This improves the previously smallest dependence on ɛ in the running time \((1/\varepsilon)^{\mathcal {O}(1/\varepsilon ^{d-1})}n \log n\) of the algorithm by Rao and Smith (STOC 1998). We also show that a \(2^{o(1/\varepsilon ^{d-1})}\mathrm{poly}(n)\) algorithm would violate the Gap-Exponential Time Hypothesis (Gap-ETH). Our new algorithm builds upon the celebrated quadtree-based methods initially proposed by Arora (J. ACM 1998), but it adds a new idea that we call sparsity-sensitive patching . On a high level this lets the granularity with which we simplify the tour depend on how sparse it is locally. We demonstrate that our technique extends to other problems, by showing that for Steiner Tree and Rectilinear Steiner Tree it yields the same running time. We complement our results with a matching Gap-ETH lower bound for Rectilinear Steiner Tree. - Open Access
- 9 October 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (5) , 1-27
Coverability in VASS Revisited: Improving Rackoff’s Bounds to Obtain Conditional Optimality
Seminal results establish that the coverability problem for Vector Addition Systems with States (VASS) is in EXPSPACE (Rackoff, ’78) and is EXPSPACE -hard already under unary encodings (Lipton, ’76). More precisely, Rosier and Yen later utilise Rackoff’s bounding technique to show that if coverability holds then there is a run of length at most \(n^{2^{\mathcal {O}(d \log (d))}}\) , where d is the dimension and n is the size of the given unary VASS. Earlier, Lipton showed that there exist instances of coverability in d -dimensional unary VASS that are only witnessed by runs of length at least \(n^{2^{\Omega (d)}}\) . Our first result closes this gap. We improve the upper bound by removing the twice-exponentiated \(\log (d)\) factor, thus matching Lipton’s lower bound. This closes the corresponding gap for the exact space required to decide coverability. This also yields a deterministic \(n^{2^{\mathcal {O}(d)}}\) -time algorithm for coverability. Our second result is a matching lower bound, that there does not exist a deterministic \(n^{2^{o(d)}}\) -time algorithm, conditioned upon the exponential time hypothesis. When analysing coverability, a standard proof technique is to consider VASS with bounded counters. Bounded VASS make for an interesting and popular model due to strong connections with timed automata. Withal, we study a natural setting where the counter bound is linear in the size of the VASS. Here the trivial exhaustive search algorithm runs in \(\mathcal {O}(n^{d+1})\) time. We give evidence to this being near-optimal. We prove that in dimension one this trivial algorithm is conditionally optimal, by showing that \(n^{2-o(1)}\) time is required under the k -cycle hypothesis. In general, for any fixed dimension d ≥ 4, we show that \(n^{d-2-o(1)}\) time is required under the 3-uniform hyperclique hypothesis.- 9 October 2025
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (5) , 1-27
Open AccessCoverability in VASS Revisited: Improving Rackoff’s Bounds to Obtain Conditional Optimality
Seminal results establish that the coverability problem for Vector Addition Systems with States (VASS) is in EXPSPACE (Rackoff, ’78) and is EXPSPACE -hard already under unary encodings (Lipton, ’76). More precisely, Rosier and Yen later utilise Rackoff’s bounding technique to show that if coverability holds then there is a run of length at most \(n^{2^{\mathcal {O}(d \log (d))}}\) , where d is the dimension and n is the size of the given unary VASS. Earlier, Lipton showed that there exist instances of coverability in d -dimensional unary VASS that are only witnessed by runs of length at least \(n^{2^{\Omega (d)}}\) . Our first result closes this gap. We improve the upper bound by removing the twice-exponentiated \(\log (d)\) factor, thus matching Lipton’s lower bound. This closes the corresponding gap for the exact space required to decide coverability. This also yields a deterministic \(n^{2^{\mathcal {O}(d)}}\) -time algorithm for coverability. Our second result is a matching lower bound, that there does not exist a deterministic \(n^{2^{o(d)}}\) -time algorithm, conditioned upon the exponential time hypothesis. When analysing coverability, a standard proof technique is to consider VASS with bounded counters. Bounded VASS make for an interesting and popular model due to strong connections with timed automata. Withal, we study a natural setting where the counter bound is linear in the size of the VASS. Here the trivial exhaustive search algorithm runs in \(\mathcal {O}(n^{d+1})\) time. We give evidence to this being near-optimal. We prove that in dimension one this trivial algorithm is conditionally optimal, by showing that \(n^{2-o(1)}\) time is required under the k -cycle hypothesis. In general, for any fixed dimension d ≥ 4, we show that \(n^{d-2-o(1)}\) time is required under the 3-uniform hyperclique hypothesis. - Open Access
The Tractability Border of Reachability in Simple Vector Addition Systems with States
Vector Addition Systems with States (VASS), equivalent to Petri nets, are a well-established model of concurrency. The central algorithmic challenge in VASS is the reachability problem: is there a run from a given starting state and counter values to a given target state and counter values? When the input is encoded in binary, reachability is computationally intractable: even in dimension one, it is NP-hard. In this paper, we comprehensively characterise the tractability border of the problem when the input is encoded in unary. For our main result, we prove that reachability is NP-hard in unary encoded 3-VASS, even when structure is heavily restricted to be a simple linear path scheme. This improves upon a recent result of Czerwiński and Orlikowski (2022), in both the number of counters and expressiveness of the considered model, as well as answers open questions of Englert, Lazić, and Totzke (2016) and Leroux (2021). The underlying graph structure of a simple linear path scheme (SLPS) is just a path with self-loops at each node. We also study the exceedingly weak model of computation that is SPLS with counter updates in {-1,0,+1}. Here, we show that reachability is NP-hard when the dimension is bounded by O(α(k)), where αis the inverse Ackermann function and k bounds the size of the SLPS. We complement our result by presenting a polynomial-time algorithm that decides reachability in 2-SLPS when the initial and target configurations are specified in binary. To achieve this, we show that reachability in such instances is well-structured: all loops, except perhaps for a constant number, are taken either polynomially many times or almost maximally. This extends the main result of Englert, Lazić, and Totzke (2016) who showed the problem is in NL when the initial and target configurations are specified in unary.
Open AccessThe Tractability Border of Reachability in Simple Vector Addition Systems with States
Vector Addition Systems with States (VASS), equivalent to Petri nets, are a well-established model of concurrency. The central algorithmic challenge in VASS is the reachability problem: is there a run from a given starting state and counter values to a given target state and counter values? When the input is encoded in binary, reachability is computationally intractable: even in dimension one, it is NP-hard. In this paper, we comprehensively characterise the tractability border of the problem when the input is encoded in unary. For our main result, we prove that reachability is NP-hard in unary encoded 3-VASS, even when structure is heavily restricted to be a simple linear path scheme. This improves upon a recent result of Czerwiński and Orlikowski (2022), in both the number of counters and expressiveness of the considered model, as well as answers open questions of Englert, Lazić, and Totzke (2016) and Leroux (2021). The underlying graph structure of a simple linear path scheme (SLPS) is just a path with self-loops at each node. We also study the exceedingly weak model of computation that is SPLS with counter updates in {-1,0,+1}. Here, we show that reachability is NP-hard when the dimension is bounded by O(α(k)), where αis the inverse Ackermann function and k bounds the size of the SLPS. We complement our result by presenting a polynomial-time algorithm that decides reachability in 2-SLPS when the initial and target configurations are specified in binary. To achieve this, we show that reachability in such instances is well-structured: all loops, except perhaps for a constant number, are taken either polynomially many times or almost maximally. This extends the main result of Englert, Lazić, and Totzke (2016) who showed the problem is in NL when the initial and target configurations are specified in unary.
- Open Access
Improving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach
Lagarias and Odlyzko (J.~ACM~1985) proposed a polynomial time algorithm for solving ``\emph{almost all}'' instances of the Subset Sum problem with $n$ integers of size $Ω(Γ_{\text{LO}})$, where $\log_2(Γ_{\text{LO}}) > n^2 \log_2(γ)$ and $γ$ is a parameter of the lattice basis reduction ($γ> \sqrt{4/3}$ for LLL). The algorithm of Lagarias and Odlyzko is a cornerstone result in cryptography. However, the theoretical guarantee on the density of feasible instances has remained unimproved for almost 40 years. In this paper, we propose an algorithm to solve ``almost all'' instances of Subset Sum with integers of size $Ω(\sqrt{Γ_{\text{LO}}})$ after a single call to the lattice reduction. Additionally, our argument allows us to solve the Subset Sum problem for multiple targets while the previous approach could only answer one target per call to lattice basis reduction. We introduce a modular arithmetic approach to the Subset Sum problem. The idea is to use the lattice reduction to solve a linear system modulo a suitably large prime. We show that density guarantees can be improved, by analysing the lengths of the LLL reduced basis vectors, of both the primal and the dual lattices simultaneously.Open AccessImproving Lagarias-Odlyzko Algorithm For Average-Case Subset Sum: Modular Arithmetic Approach
Lagarias and Odlyzko (J.~ACM~1985) proposed a polynomial time algorithm for solving ``\emph{almost all}'' instances of the Subset Sum problem with $n$ integers of size $Ω(Γ_{\text{LO}})$, where $\log_2(Γ_{\text{LO}}) > n^2 \log_2(γ)$ and $γ$ is a parameter of the lattice basis reduction ($γ> \sqrt{4/3}$ for LLL). The algorithm of Lagarias and Odlyzko is a cornerstone result in cryptography. However, the theoretical guarantee on the density of feasible instances has remained unimproved for almost 40 years. In this paper, we propose an algorithm to solve ``almost all'' instances of Subset Sum with integers of size $Ω(\sqrt{Γ_{\text{LO}}})$ after a single call to the lattice reduction. Additionally, our argument allows us to solve the Subset Sum problem for multiple targets while the previous approach could only answer one target per call to lattice basis reduction. We introduce a modular arithmetic approach to the Subset Sum problem. The idea is to use the lattice reduction to solve a linear system modulo a suitably large prime. We show that density guarantees can be improved, by analysing the lengths of the LLL reduced basis vectors, of both the primal and the dual lattices simultaneously. - Open Access
Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM
We study the parameterized complexity of algorithmic problems whose input is an integer set $A$ in terms of the doubling constant $C := |A + A|/|A|$, a fundamental measure of additive structure. We present evidence that this new parameterization is algorithmically useful in the form of new results for two difficult, well-studied problems: Integer Programming and Subset Sum. First, we show that determining the feasibility of bounded Integer Programs is a tractable problem when parameterized in the doubling constant. Specifically, we prove that the feasibility of an integer program $I$ with $n$ polynomially-bounded variables and $m$ constraints can be determined in time $n^{O_C(1)} poly(|I|)$ when the column set of the constraint matrix has doubling constant $C$. Second, we show that the Subset Sum and Unbounded Subset Sum problems can be solved in time $n^{O_C(1)}$ and $n^{O_C(\log \log \log n)}$, respectively, where the $O_C$ notation hides functions that depend only on the doubling constant $C$. We also show the equivalence of achieving an FPT algorithm for Subset Sum with bounded doubling and achieving a milestone result for the parameterized complexity of Box ILP. Finally, we design near-linear time algorithms for $k$-SUM as well as tight lower bounds for 4-SUM and nearly tight lower bounds for $k$-SUM, under the $k$-SUM conjecture. Several of our results rely on a new proof that Freiman's Theorem, a central result in additive combinatorics, can be made efficiently constructive. This result may be of independent interest.Open AccessParameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM
We study the parameterized complexity of algorithmic problems whose input is an integer set $A$ in terms of the doubling constant $C := |A + A|/|A|$, a fundamental measure of additive structure. We present evidence that this new parameterization is algorithmically useful in the form of new results for two difficult, well-studied problems: Integer Programming and Subset Sum. First, we show that determining the feasibility of bounded Integer Programs is a tractable problem when parameterized in the doubling constant. Specifically, we prove that the feasibility of an integer program $I$ with $n$ polynomially-bounded variables and $m$ constraints can be determined in time $n^{O_C(1)} poly(|I|)$ when the column set of the constraint matrix has doubling constant $C$. Second, we show that the Subset Sum and Unbounded Subset Sum problems can be solved in time $n^{O_C(1)}$ and $n^{O_C(\log \log \log n)}$, respectively, where the $O_C$ notation hides functions that depend only on the doubling constant $C$. We also show the equivalence of achieving an FPT algorithm for Subset Sum with bounded doubling and achieving a milestone result for the parameterized complexity of Box ILP. Finally, we design near-linear time algorithms for $k$-SUM as well as tight lower bounds for 4-SUM and nearly tight lower bounds for $k$-SUM, under the $k$-SUM conjecture. Several of our results rely on a new proof that Freiman's Theorem, a central result in additive combinatorics, can be made efficiently constructive. This result may be of independent interest. - Open Access
A polynomial-time $\text{OPT}^ε$-approximation algorithm for maximum independent set of connected subgraphs in a planar graph
In the Maximum Independent Set of Objects problem, we are given an $n$-vertex planar graph $G$ and a family $\mathcal{D}$ of $N$ objects, where each object is a connected subgraph of $G$. The task is to find a subfamily $\mathcal{F} \subseteq \mathcal{D}$ of maximum cardinality that consists of pairwise disjoint objects. This problem is $\mathsf{NP}$-hard and is equivalent to the problem of finding the maximum number of pairwise disjoint polygons in a given family of polygons in the plane. As shown by Adamaszek et al. (J. ACM '19), the problem admits a \emph{quasi-polynomial time approximation scheme} (QPTAS): a $(1-\varepsilon)$-approximation algorithm whose running time is bounded by $2^{\mathrm{poly}(\log(N),1/ε)} \cdot n^{\mathcal{O}(1)}$. Nevertheless, to the best of our knowledge, in the polynomial-time regime only the trivial $\mathcal{O}(N)$-approximation is known for the problem in full generality. In the restricted setting where the objects are pseudolines in the plane, Fox and Pach (SODA '11) gave an $N^{\varepsilon}$-approximation algorithm with running time $N^{2^{\tilde{\mathcal{O}}(1/\varepsilon)}}$, for any $\varepsilon>0$. In this work, we present an $\text{OPT}^{\varepsilon}$-approximation algorithm for the problem that runs in time $N^{\tilde{\mathcal{O}}(1/\varepsilon^2)} n^{\mathcal{O}(1)}$, for any $\varepsilon>0$, thus improving upon the result of Fox and Pach both in terms of generality and in terms of the running time. Our approach combines the methodology of Voronoi separators, introduced by Marx and Pilipczuk (TALG '22), with a new analysis of the approximation factor.Open AccessA polynomial-time $\text{OPT}^ε$-approximation algorithm for maximum independent set of connected subgraphs in a planar graph
In the Maximum Independent Set of Objects problem, we are given an $n$-vertex planar graph $G$ and a family $\mathcal{D}$ of $N$ objects, where each object is a connected subgraph of $G$. The task is to find a subfamily $\mathcal{F} \subseteq \mathcal{D}$ of maximum cardinality that consists of pairwise disjoint objects. This problem is $\mathsf{NP}$-hard and is equivalent to the problem of finding the maximum number of pairwise disjoint polygons in a given family of polygons in the plane. As shown by Adamaszek et al. (J. ACM '19), the problem admits a \emph{quasi-polynomial time approximation scheme} (QPTAS): a $(1-\varepsilon)$-approximation algorithm whose running time is bounded by $2^{\mathrm{poly}(\log(N),1/ε)} \cdot n^{\mathcal{O}(1)}$. Nevertheless, to the best of our knowledge, in the polynomial-time regime only the trivial $\mathcal{O}(N)$-approximation is known for the problem in full generality. In the restricted setting where the objects are pseudolines in the plane, Fox and Pach (SODA '11) gave an $N^{\varepsilon}$-approximation algorithm with running time $N^{2^{\tilde{\mathcal{O}}(1/\varepsilon)}}$, for any $\varepsilon>0$. In this work, we present an $\text{OPT}^{\varepsilon}$-approximation algorithm for the problem that runs in time $N^{\tilde{\mathcal{O}}(1/\varepsilon^2)} n^{\mathcal{O}(1)}$, for any $\varepsilon>0$, thus improving upon the result of Fox and Pach both in terms of generality and in terms of the running time. Our approach combines the methodology of Voronoi separators, introduced by Marx and Pilipczuk (TALG '22), with a new analysis of the approximation factor. - Open Access
Separator Theorem and Algorithms for Planar Hyperbolic Graphs
The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incomparable. Motivated by the broad study of algorithms and separators on planar graphs and their relation to treewidth, we initiate the study of planar graphs of bounded hyperbolicity. Our main technical contribution is a novel balanced separator theorem for planar $\delta$-hyperbolic graphs that is substantially stronger than the classic planar separator theorem. For any fixed $\delta \geq 0$, we can find balanced separator that induces either a single geodesic (shortest) path or a single geodesic cycle in the graph. An important advantage of our separator is that the union of our separator (vertex set $Z$) with any subset of the connected components of $G - Z$ induces again a planar $\delta$-hyperbolic graph, which would not be guaranteed with an arbitrary separator. Our construction runs in near-linear time and guarantees that size of separator is $\mathrm{poly}(\delta) \cdot \log n$. As an application of our separator theorem and its strong properties, we obtain two novel approximation schemes on planar $\delta$-hyperbolic graphs. We prove that Maximum Independent Set and the Traveling Salesperson problem have a near-linear time FPTAS for any constant $\delta$, running in $n\, \mathrm{polylog}(n) \cdot 2^{\mathcal{O}(\delta^2)} \cdot \varepsilon^{-\mathcal{O}(\delta)}$ time. We also show that our approximation scheme for Maximum Independent Set has essentially the best possible running time under the Exponential Time Hypothesis (ETH). This immediately follows from our third contribution: we prove that Maximum Independent Set has no $n^{o(\delta)}$-time algorithm on planar $\delta$-hyperbolic graphs, unless ETH fails.Open AccessSeparator Theorem and Algorithms for Planar Hyperbolic Graphs
The hyperbolicity of a graph, informally, measures how close a graph is (metrically) to a tree. Hence, it is intuitively similar to treewidth, but the measures are formally incomparable. Motivated by the broad study of algorithms and separators on planar graphs and their relation to treewidth, we initiate the study of planar graphs of bounded hyperbolicity. Our main technical contribution is a novel balanced separator theorem for planar $\delta$-hyperbolic graphs that is substantially stronger than the classic planar separator theorem. For any fixed $\delta \geq 0$, we can find balanced separator that induces either a single geodesic (shortest) path or a single geodesic cycle in the graph. An important advantage of our separator is that the union of our separator (vertex set $Z$) with any subset of the connected components of $G - Z$ induces again a planar $\delta$-hyperbolic graph, which would not be guaranteed with an arbitrary separator. Our construction runs in near-linear time and guarantees that size of separator is $\mathrm{poly}(\delta) \cdot \log n$. As an application of our separator theorem and its strong properties, we obtain two novel approximation schemes on planar $\delta$-hyperbolic graphs. We prove that Maximum Independent Set and the Traveling Salesperson problem have a near-linear time FPTAS for any constant $\delta$, running in $n\, \mathrm{polylog}(n) \cdot 2^{\mathcal{O}(\delta^2)} \cdot \varepsilon^{-\mathcal{O}(\delta)}$ time. We also show that our approximation scheme for Maximum Independent Set has essentially the best possible running time under the Exponential Time Hypothesis (ETH). This immediately follows from our third contribution: we prove that Maximum Independent Set has no $n^{o(\delta)}$-time algorithm on planar $\delta$-hyperbolic graphs, unless ETH fails.