Search Results

Documents authored by Kisfaludi-Bak, Sándor

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.67
Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification

Authors: Esther Galby, Sándor Kisfaludi-Bak, Dániel Marx, and Roohani Sharma

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In the Directed Steiner Network problem, the input is a directed graph G, a set T ⊆ V(G) of k terminals, and a demand graph D on T. The task is to find a subgraph H ⊆ G with the minimum number of edges such that for every (s,t) ∈ E(D), the solution H contains a directed s → t path. The goal of this paper is to investigate how the complexity of the problem depends on the demand pattern in planar graphs. Formally, if 𝒟 is a class of directed graphs, then the 𝒟-Steiner Network (𝒟-DSN) problem is the special case where the demand graph D is restricted to be from 𝒟. We give a complete characterization of the behavior of every 𝒟-DSN problem on planar graphs. We classify every class 𝒟 closed under transitive equivalence and identification of vertices into three cases: assuming ETH, either the problem is 1) solvable in time 2^O(k)⋅n^O(1), i.e., FPT parameterized by the number k of terminals, but not solvable in time 2^o(k)⋅n^O(1), 2) solvable in time f(k)⋅n^O(√k), but cannot be solved in time f(k)⋅n^o(√k), or 3) solvable in time f(k)⋅n^O(k), but cannot be solved in time f(k)⋅n^o(k). Our result is a far-reaching generalization and unification of earlier results on Directed Steiner Tree, Directed Steiner Network, and Strongly Connected Steiner Subgraph on planar graphs. As an important step of our lower bound proof, we discover a rare example of a genuinely planar problem (i.e., described by a planar graph and two sets of vertices) that cannot be solved in time f(k)⋅n^o(k): given two sets of terminals S and T with |S|+|T| = k, find a subgraph with minimum number of edges such that every vertex of T is reachable from every vertex of S.
Cite as

Esther Galby, Sándor Kisfaludi-Bak, Dániel Marx, and Roohani Sharma. Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{galby_et_al:LIPIcs.ICALP.2024.67,
  author =	{Galby, Esther and Kisfaludi-Bak, S\'{a}ndor and Marx, D\'{a}niel and Sharma, Roohani},
  title =	{{Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: A Complete Classification}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{67:1--67:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.67},
  URN =		{urn:nbn:de:0030-drops-202104},
  doi =		{10.4230/LIPIcs.ICALP.2024.67},
  annote =	{Keywords: Directed Steiner Network, Sub-exponential algorithm}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.67
Separator Theorem and Algorithms for Planar Hyperbolic Graphs

Authors: Sándor Kisfaludi-Bak, Jana Masaříková, Erik Jan van Leeuwen, Bartosz Walczak, and Karol Węgrzycki

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
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 δ-hyperbolic graphs that is substantially stronger than the classic planar separator theorem. For any fixed δ ⩾ 0, we can find a small 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 δ-hyperbolic graph, which would not be guaranteed with an arbitrary separator. Our construction runs in near-linear time and guarantees that the size of the separator is poly(δ) ⋅ log n. As an application of our separator theorem and its strong properties, we obtain two novel approximation schemes on planar δ-hyperbolic graphs. We prove that both Maximum Independent Set and the Traveling Salesperson problem have a near-linear time FPTAS for any constant δ, running in n polylog(n) ⋅ 2^𝒪(δ²) ⋅ ε^{-𝒪(δ)} 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(δ)}-time algorithm on planar δ-hyperbolic graphs, unless ETH fails.
Cite as

Sándor Kisfaludi-Bak, Jana Masaříková, Erik Jan van Leeuwen, Bartosz Walczak, and Karol Węgrzycki. Separator Theorem and Algorithms for Planar Hyperbolic Graphs. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 67:1-67:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kisfaludibak_et_al:LIPIcs.SoCG.2024.67,
  author =	{Kisfaludi-Bak, S\'{a}ndor and Masa\v{r}{\'\i}kov\'{a}, Jana and van Leeuwen, Erik Jan and Walczak, Bartosz and W\k{e}grzycki, Karol},
  title =	{{Separator Theorem and Algorithms for Planar Hyperbolic Graphs}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{67:1--67:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.67},
  URN =		{urn:nbn:de:0030-drops-200126},
  doi =		{10.4230/LIPIcs.SoCG.2024.67},
  annote =	{Keywords: Hyperbolic metric, Planar Graphs, r-Division, Approximation Algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.68
A Quadtree, a Steiner Spanner, and Approximate Nearest Neighbours in Hyperbolic Space

Authors: Sándor Kisfaludi-Bak and Geert van Wordragen

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
We propose a data structure in d-dimensional hyperbolic space that can be considered a natural counterpart to quadtrees in Euclidean spaces. Based on this data structure we propose a so-called L-order for hyperbolic point sets, which is an extension of the Z-order defined in Euclidean spaces. Using these quadtrees and the L-order we build geometric spanners. Near-linear size (1+ε)-spanners do not exist in hyperbolic spaces, but we create a Steiner spanner that achieves a spanning ratio of 1+ε with O_{d,ε}(n) edges, using a simple construction that can be maintained dynamically. As a corollary we also get a (2+ε)-spanner (in the classical sense) of the same size, where the spanning ratio 2+ε is almost optimal among spanners of subquadratic size. Finally, we show that our Steiner spanner directly provides an elegant solution to the approximate nearest neighbour problem: given a point set P in d-dimensional hyperbolic space we build the data structure in O_{d,ε}(nlog n) time, using O_{d,ε}(n) space. Then for any query point q we can find a point p ∈ P that is at most 1+ε times farther from q than its nearest neighbour in P in O_{d,ε}(log n) time. Moreover, the data structure is dynamic and can handle point insertions and deletions with update time O_{d,ε}(log n). This is the first dynamic nearest neighbour data structure in hyperbolic space with proven efficiency guarantees.
Cite as

Sándor Kisfaludi-Bak and Geert van Wordragen. A Quadtree, a Steiner Spanner, and Approximate Nearest Neighbours in Hyperbolic Space. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 68:1-68:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kisfaludibak_et_al:LIPIcs.SoCG.2024.68,
  author =	{Kisfaludi-Bak, S\'{a}ndor and van Wordragen, Geert},
  title =	{{A Quadtree, a Steiner Spanner, and Approximate Nearest Neighbours in Hyperbolic Space}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{68:1--68:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.68},
  URN =		{urn:nbn:de:0030-drops-200133},
  doi =		{10.4230/LIPIcs.SoCG.2024.68},
  annote =	{Keywords: hyperbolic geometry, Steiner spanner, dynamic approximate nearest neighbours}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.9
Computing Smallest Convex Intersecting Polygons

Authors: Antonios Antoniadis, Mark de Berg, Sándor Kisfaludi-Bak, and Antonis Skarlatos

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
A polygon C is an intersecting polygon for a set O of objects in ℝ² if C intersects each object in O, where the polygon includes its interior. We study the problem of computing the minimum-perimeter intersecting polygon and the minimum-area convex intersecting polygon for a given set O of objects. We present an FPTAS for both problems for the case where O is a set of possibly intersecting convex polygons in the plane of total complexity n. Furthermore, we present an exact polynomial-time algorithm for the minimum-perimeter intersecting polygon for the case where O is a set of n possibly intersecting segments in the plane. So far, polynomial-time exact algorithms were only known for the minimum perimeter intersecting polygon of lines or of disjoint segments.
Cite as

Antonios Antoniadis, Mark de Berg, Sándor Kisfaludi-Bak, and Antonis Skarlatos. Computing Smallest Convex Intersecting Polygons. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 9:1-9:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.ESA.2022.9,
  author =	{Antoniadis, Antonios and de Berg, Mark and Kisfaludi-Bak, S\'{a}ndor and Skarlatos, Antonis},
  title =	{{Computing Smallest Convex Intersecting Polygons}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{9:1--9:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.9},
  URN =		{urn:nbn:de:0030-drops-169470},
  doi =		{10.4230/LIPIcs.ESA.2022.9},
  annote =	{Keywords: convex hull, imprecise points, computational geometry}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.10
On the Approximability of the Traveling Salesman Problem with Line Neighborhoods

Authors: Antonios Antoniadis, Sándor Kisfaludi-Bak, Bundit Laekhanukit, and Daniel Vaz

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
We study the variant of the Euclidean Traveling Salesman problem where instead of a set of points, we are given a set of lines as input, and the goal is to find the shortest tour that visits each line. The best known upper and lower bounds for the problem in ℝ^d, with d ≥ 3, are NP-hardness and an O(log³ n)-approximation algorithm which is based on a reduction to the group Steiner tree problem. We show that TSP with lines in ℝ^d is APX-hard for any d ≥ 3. More generally, this implies that TSP with k-dimensional flats does not admit a PTAS for any 1 ≤ k ≤ d-2 unless P = NP, which gives a complete classification regarding the existence of polynomial time approximation schemes for these problems, as there are known PTASes for k = 0 (i.e., points) and k = d-1 (hyperplanes). We are able to give a stronger inapproximability factor for d = O(log n) by showing that TSP with lines does not admit a (2-ε)-approximation in d dimensions under the Unique Games Conjecture. On the positive side, we leverage recent results on restricted variants of the group Steiner tree problem in order to give an O(log² n)-approximation algorithm for the problem, albeit with a running time of n^{O(log log n)}.
Cite as

Antonios Antoniadis, Sándor Kisfaludi-Bak, Bundit Laekhanukit, and Daniel Vaz. On the Approximability of the Traveling Salesman Problem with Line Neighborhoods. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.SWAT.2022.10,
  author =	{Antoniadis, Antonios and Kisfaludi-Bak, S\'{a}ndor and Laekhanukit, Bundit and Vaz, Daniel},
  title =	{{On the Approximability of the Traveling Salesman Problem with Line Neighborhoods}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.10},
  URN =		{urn:nbn:de:0030-drops-161706},
  doi =		{10.4230/LIPIcs.SWAT.2022.10},
  annote =	{Keywords: Traveling Salesman with neighborhoods, Group Steiner Tree, Geometric approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.22
Clique-Based Separators for Geometric Intersection Graphs

Authors: Mark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh, and Leonidas Theocharous

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
Let F be a set of n objects in the plane and let 𝒢^{×}(F) be its intersection graph. A balanced clique-based separator of 𝒢^{×}(F) is a set 𝒮 consisting of cliques whose removal partitions 𝒢^{×}(F) into components of size at most δ n, for some fixed constant δ < 1. The weight of a clique-based separator is defined as ∑_{C ∈ 𝒮}log (|C|+1). Recently De Berg et al. (SICOMP 2020) proved that if S consists of convex fat objects, then 𝒢^{×}(F) admits a balanced clique-based separator of weight O(√n). We extend this result in several directions, obtaining the following results. - Map graphs admit a balanced clique-based separator of weight O(√n), which is tight in the worst case. - Intersection graphs of pseudo-disks admit a balanced clique-based separator of weight O(n^{2/3} log n). If the pseudo-disks are polygonal and of total complexity O(n) then the weight of the separator improves to O(√n log n). - Intersection graphs of geodesic disks inside a simple polygon admit a balanced clique-based separator of weight O(n^{2/3} log n). - Visibility-restricted unit-disk graphs in a polygonal domain with r reflex vertices admit a balanced clique-based separator of weight O(√n + r log(n/r)), which is tight in the worst case. These results immediately imply sub-exponential algorithms for MAXIMUM INDEPENDENT SET (and, hence, VERTEX COVER), for FEEDBACK VERTEX SET, and for q-Coloring for constant q in these graph classes.
Cite as

Mark de Berg, Sándor Kisfaludi-Bak, Morteza Monemizadeh, and Leonidas Theocharous. Clique-Based Separators for Geometric Intersection Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ISAAC.2021.22,
  author =	{de Berg, Mark and Kisfaludi-Bak, S\'{a}ndor and Monemizadeh, Morteza and Theocharous, Leonidas},
  title =	{{Clique-Based Separators for Geometric Intersection Graphs}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{22:1--22:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.22},
  URN =		{urn:nbn:de:0030-drops-154556},
  doi =		{10.4230/LIPIcs.ISAAC.2021.22},
  annote =	{Keywords: Computational geometry, intersection graphs, separator theorems}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.4
Euclidean TSP in Narrow Strips

Authors: Henk Alkema, Mark de Berg, and Sándor Kisfaludi-Bak

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We investigate how the complexity of {Euclidean TSP} for point sets P inside the strip (-∞,+∞)×[0,δ] depends on the strip width δ. We obtain two main results. - For the case where the points have distinct integer x-coordinates, we prove that a shortest bitonic tour (which can be computed in O(n log²n) time using an existing algorithm) is guaranteed to be a shortest tour overall when δ ⩽ 2√2, a bound which is best possible. - We present an algorithm that is fixed-parameter tractable with respect to δ. More precisely, our algorithm has running time 2^{O(√δ)} n² for sparse point sets, where each 1×δ rectangle inside the strip contains O(1) points. For random point sets, where the points are chosen uniformly at random from the rectangle [0,n]× [0,δ], it has an expected running time of 2^{O(√δ)} n² + O(n³).
Cite as

Henk Alkema, Mark de Berg, and Sándor Kisfaludi-Bak. Euclidean TSP in Narrow Strips. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{alkema_et_al:LIPIcs.SoCG.2020.4,
  author =	{Alkema, Henk and de Berg, Mark and Kisfaludi-Bak, S\'{a}ndor},
  title =	{{Euclidean TSP in Narrow Strips}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.4},
  URN =		{urn:nbn:de:0030-drops-121628},
  doi =		{10.4230/LIPIcs.SoCG.2020.4},
  annote =	{Keywords: Computational geometry, Euclidean TSP, bitonic TSP, fixed-parameter tractable algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.55
A Quasi-Polynomial Algorithm for Well-Spaced Hyperbolic TSP

Authors: Sándor Kisfaludi-Bak

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
We study the traveling salesman problem in the hyperbolic plane of Gaussian curvature -1. Let α denote the minimum distance between any two input points. Using a new separator theorem and a new rerouting argument, we give an n^{O(log² n)max(1,1/α)} algorithm for Hyperbolic TSP. This is quasi-polynomial time if α is at least some absolute constant, and it grows to n^O(√n) as α decreases to log² n/√n. (For even smaller values of α, we can use a planarity-based algorithm of Hwang et al. (1993), which gives a running time of n^O(√n).)
Cite as

Sándor Kisfaludi-Bak. A Quasi-Polynomial Algorithm for Well-Spaced Hyperbolic TSP. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kisfaludibak:LIPIcs.SoCG.2020.55,
  author =	{Kisfaludi-Bak, S\'{a}ndor},
  title =	{{A Quasi-Polynomial Algorithm for Well-Spaced Hyperbolic TSP}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.55},
  URN =		{urn:nbn:de:0030-drops-122135},
  doi =		{10.4230/LIPIcs.SoCG.2020.55},
  annote =	{Keywords: Computational geometry, Hyperbolic geometry, Traveling salesman}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.36
How Does Object Fatness Impact the Complexity of Packing in d Dimensions?

Authors: Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
Packing is a classical problem where one is given a set of subsets of Euclidean space called objects, and the goal is to find a maximum size subset of objects that are pairwise non-intersecting. The problem is also known as the Independent Set problem on the intersection graph defined by the objects. Although the problem is NP-complete, there are several subexponential algorithms in the literature. One of the key assumptions of such algorithms has been that the objects are fat, with a few exceptions in two dimensions; for example, the packing problem of a set of polygons in the plane surprisingly admits a subexponential algorithm. In this paper we give tight running time bounds for packing similarly-sized non-fat objects in higher dimensions. We propose an alternative and very weak measure of fatness called the stabbing number, and show that the packing problem in Euclidean space of constant dimension d >=slant 3 for a family of similarly sized objects with stabbing number alpha can be solved in 2^O(n^(1-1/d) alpha) time. We prove that even in the case of axis-parallel boxes of fixed shape, there is no 2^o(n^(1-1/d) alpha) algorithm under ETH. This result smoothly bridges the whole range of having constant-fat objects on one extreme (alpha=1) and a subexponential algorithm of the usual running time, and having very "skinny" objects on the other extreme (alpha=n^(1/d)), where we cannot hope to improve upon the brute force running time of 2^O(n), and thereby characterizes the impact of fatness on the complexity of packing in case of similarly sized objects. We also study the same problem when parameterized by the solution size k, and give a n^O(k^(1-1/d) alpha) algorithm, with an almost matching lower bound: there is no algorithm with running time of the form f(k) n^o(k^(1-1/d) alpha/log k) under ETH. One of our main tools in these reductions is a new wiring theorem that may be of independent interest.
Cite as

Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden. How Does Object Fatness Impact the Complexity of Packing in d Dimensions?. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{kisfaludibak_et_al:LIPIcs.ISAAC.2019.36,
  author =	{Kisfaludi-Bak, S\'{a}ndor and Marx, D\'{a}niel and van der Zanden, Tom C.},
  title =	{{How Does Object Fatness Impact the Complexity of Packing in d Dimensions?}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{36:1--36:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.36},
  URN =		{urn:nbn:de:0030-drops-115327},
  doi =		{10.4230/LIPIcs.ISAAC.2019.36},
  annote =	{Keywords: Geometric intersection graph, Independent Set, Object fatness}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2019.37
On One-Round Discrete Voronoi Games

Authors: Mark de Berg, Sándor Kisfaludi-Bak, and Mehran Mehr

Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)

Abstract
Let V be a multiset of n points in R^d, which we call voters, and let k >=slant 1 and l >=slant 1 be two given constants. We consider the following game, where two players P and Q compete over the voters in V: First, player P selects a set P of k points in R^d, and then player Q selects a set Q of l points in R^d. Player P wins a voter v in V iff dist(v,P) <=slant dist(v,Q), where dist(v,P) := min_{p in P} dist(v,p) and dist(v,Q) is defined similarly. Player P wins the game if he wins at least half the voters. The algorithmic problem we study is the following: given V, k, and l, how efficiently can we decide if player P has a winning strategy, that is, if P can select his k points such that he wins the game no matter where Q places her points. Banik et al. devised a singly-exponential algorithm for the game in R^1, for the case k=l. We improve their result by presenting the first polynomial-time algorithm for the game in R^1. Our algorithm can handle arbitrary values of k and l. We also show that if d >= 2, deciding if player P has a winning strategy is Sigma_2^P-hard when k and l are part of the input. Finally, we prove that for any dimension d, the problem is contained in the complexity class exists for all R, and we give an algorithm that works in polynomial time for fixed k and l.
Cite as

Mark de Berg, Sándor Kisfaludi-Bak, and Mehran Mehr. On One-Round Discrete Voronoi Games. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 37:1-37:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ISAAC.2019.37,
  author =	{de Berg, Mark and Kisfaludi-Bak, S\'{a}ndor and Mehr, Mehran},
  title =	{{On One-Round Discrete Voronoi Games}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{37:1--37:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Lu, Pinyan and Zhang, Guochuan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.37},
  URN =		{urn:nbn:de:0030-drops-115339},
  doi =		{10.4230/LIPIcs.ISAAC.2019.37},
  annote =	{Keywords: competitive facility location, plurality point}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.26
On Geometric Set Cover for Orthants

Authors: Karl Bringmann, Sándor Kisfaludi-Bak, Michał Pilipczuk, and Erik Jan van Leeuwen

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
We study SET COVER for orthants: Given a set of points in a d-dimensional Euclidean space and a set of orthants of the form (-infty,p_1] x ... x (-infty,p_d], select a minimum number of orthants so that every point is contained in at least one selected orthant. This problem draws its motivation from applications in multi-objective optimization problems. While for d=2 the problem can be solved in polynomial time, for d>2 no algorithm is known that avoids the enumeration of all size-k subsets of the input to test whether there is a set cover of size k. Our contribution is a precise understanding of the complexity of this problem in any dimension d >= 3, when k is considered a parameter: - For d=3, we give an algorithm with runtime n^O(sqrt{k}), thus avoiding exhaustive enumeration. - For d=3, we prove a tight lower bound of n^Omega(sqrt{k}) (assuming ETH). - For d >=slant 4, we prove a tight lower bound of n^Omega(k) (assuming ETH). Here n is the size of the set of points plus the size of the set of orthants. The first statement comes as a corollary of a more general result: an algorithm for SET COVER for half-spaces in dimension 3. In particular, we show that given a set of points U in R^3, a set of half-spaces D in R^3, and an integer k, one can decide whether U can be covered by the union of at most k half-spaces from D in time |D|^O(sqrt{k})* |U|^O(1). We also study approximation for SET COVER for orthants. While in dimension 3 a PTAS can be inferred from existing results, we show that in dimension 4 and larger, there is no 1.05-approximation algorithm with runtime f(k)* n^o(k) for any computable f, where k is the optimum.
Cite as

Karl Bringmann, Sándor Kisfaludi-Bak, Michał Pilipczuk, and Erik Jan van Leeuwen. On Geometric Set Cover for Orthants. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ESA.2019.26,
  author =	{Bringmann, Karl and Kisfaludi-Bak, S\'{a}ndor and Pilipczuk, Micha{\l} and van Leeuwen, Erik Jan},
  title =	{{On Geometric Set Cover for Orthants}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.26},
  URN =		{urn:nbn:de:0030-drops-111476},
  doi =		{10.4230/LIPIcs.ESA.2019.26},
  annote =	{Keywords: Set Cover, parameterized complexity, algorithms, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2017.14
The Dominating Set Problem in Geometric Intersection Graphs

Authors: Mark de Berg, Sándor Kisfaludi-Bak, and Gerhard Woeginger

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
We study the parameterized complexity of dominating sets in geometric intersection graphs. In one dimension, we investigate intersection graphs induced by translates of a fixed pattern Q that consists of a finite number of intervals and a finite number of isolated points. We prove that Dominating Set on such intersection graphs is polynomially solvable whenever Q contains at least one interval, and whenever Q contains no intervals and for any two point pairs in Q the distance ratio is rational. The remaining case where Q contains no intervals but does contain an irrational distance ratio is shown to be NP-complete and contained in FPT (when parameterized by the solution size). In two and higher dimensions, we prove that Dominating Set is contained in W[1] for intersection graphs of semi-algebraic sets with constant description complexity. This generalizes known results from the literature. Finally, we establish W[1]-hardness for a large class of intersection graphs.
Cite as

Mark de Berg, Sándor Kisfaludi-Bak, and Gerhard Woeginger. The Dominating Set Problem in Geometric Intersection Graphs. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.IPEC.2017.14,
  author =	{de Berg, Mark and Kisfaludi-Bak, S\'{a}ndor and Woeginger, Gerhard},
  title =	{{The Dominating Set Problem in Geometric Intersection Graphs}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.14},
  URN =		{urn:nbn:de:0030-drops-85538},
  doi =		{10.4230/LIPIcs.IPEC.2017.14},
  annote =	{Keywords: dominating set, intersection graph, W-hierarchy}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact