This workshop focuses on the intersection of two important areas in TCS, Computational Geometry and Parameterized Algorithms. In recent years, designing parameterized algorithms for geometry-related problems has become an active research direction and received considerable attention. Efficient parameterized algorithms have been obtained for many fundamental geometric problems, including art gallery problems, geometric stabbing and hitting, planar graph drawing, problems on geometric intersection graphs, geometric independent set, geometric knapsack, etc. The goal of this workshop is to highlight a subset of these interesting results and motivate further research in this direction.

Schedule:

2:40 – 3:35 Meirav Zehavi: Visibility Problems, Geometric Intersection Graphs and Graph Drawing

Abstract: We will discuss three topics in Computational Geometry that have received significant attention from the perspective of Parameterized Complexity in the past few years. First, we will consider visibility problems, focusing on Art Gallery and Terrain Guarding. Second, we will consider the design of subexponential parameterized algorithms for problems on geometric intersection graphs, particularly (unit) disk graphs. Lastly, we will discuss parameterized graph drawing problems, with emphasis on crossing minimization. For each topic, we will briefly discuss some basics and related works, as well as some technical details of a result in that area.

3:35 – 4:30 David Eppstein: Widths of Geometric Graphs

Abstract: We survey the complexity of geometric algorithms parameterized by the width of an associated graph. After a brief overview of graph width parameters and their algorithmic applications, we investigate geometric graphs for which low graph width can be guaranteed, including triangulations, polyhedra, and polytopes, neighborhood systems, and geometric random graphs. However, many other natural classes of geometric graphs can have high width. This motivates the study of geometric problems where, despite the existence of high-width instances, fast algorithms have been developed for instances of low width.

4:30 – 5 Cofee break

5 – 5:50 Huck Bennett: Parameterized Inapproximability of the Minimum Distance Problem over all Fields and the Shortest Vector Problem in all l_p Norms

Abstract: We prove that the Minimum Distance Problem (MDP) on linear codes over any fixed finite field and parameterized by the input distance bound is W[1]-hard to approximate within any constant factor. We also prove analogous results for the parameterized Shortest Vector Problem (SVP) on integer lattices. Specifically, we prove that SVP in the l_p norm is W[1]-hard to approximate within any constant factor for any fixed p >1 and W[1]-hard to approximate within a factor approaching 2 for p=1. (We show hardness under randomized reductions in each case.) These results answer the main questions left open (and explicitly posed) by Bhattacharyya, Bonnet, Egri, Ghoshal, Karthik C.S., Lin, Manurangsi, and Marx (Journal of the ACM, 2021) on the complexity of parameterized MDP and SVP. For MDP, they established similar hardness for *binary* linear codes and left the case of general fields open. For SVP in l_p norms with p > 1, they showed inapproximability within *some* constant factor (depending on p) and left open showing such hardness for arbitrary constant factors. They also left open showing W[1]-hardness even of exact SVP in the ell_1 norm. Joint work with Mahdi Cheraghchi, Venkatesan Guruswami, and João Ribeiro.

5:50 – 6:40 Maarten Loeffler: Removing Popular Faces in Curve Arrangements by Inserting one more Curve

Abstract: A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate popular faces in an arrangement by inserting a single additional curve. This turns out to be already NP-hard; however, we present a probabilistic FPT-approach in the number of such faces.

Organizers:

Sayan Bandyapadhyay Portland State University
William Lochet CNRS
Jie Xue New York University Shanghai

Workshop on Parameterized Algorithms for Geometric Problems

Part of CG week 2023(June 12-15 2023)

Schedule:

Organizers: