41 Search Results for "Xue, Jie"

Document
DOI: 10.4230/LIPIcs.ESA.2025.31
An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs

Authors: Bruce W. Brewer and Haitao Wang

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
Given in the plane a set S of n points and a set of disks centered at these points, the disk graph G(S) induced by these disks has vertex set S and an edge between two vertices if their disks intersect. Note that the disks may have different radii. We consider the problem of computing shortest paths from a source point s ∈ S to all vertices in G(S) where the length of a path in G(S) is defined as the number of edges in the path. The previously best algorithm solves the problem in O(nlog² n) time. A lower bound of Ω(nlog n) is also known for this problem under the algebraic decision tree model. In this paper, we present an O(nlog n) time algorithm, which matches the lower bound and thus is optimal. Another virtue of our algorithm is that it is quite simple.
Cite as

Bruce W. Brewer and Haitao Wang. An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 31:1-31:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brewer_et_al:LIPIcs.ESA.2025.31,
  author =	{Brewer, Bruce W. and Wang, Haitao},
  title =	{{An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{31:1--31:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.31},
  URN =		{urn:nbn:de:0030-drops-244997},
  doi =		{10.4230/LIPIcs.ESA.2025.31},
  annote =	{Keywords: disk graphs, weighted Voronoi diagrams, shortest paths}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.21
A Unified FPT Framework for Crossing Number Problems

Authors: Éric Colin de Verdière and Petr Hliněný

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
The basic (and traditional) crossing number problem is to determine the minimum number of crossings in a topological drawing of an input graph in the plane. We develop a unified framework that smoothly captures many generalized crossing number problems, and that yields fixed-parameter tractable (FPT) algorithms for them not only in the plane but also on surfaces. Our framework takes the following form. We fix a surface S, an integer r, and a map κ from the set of topological drawings of graphs in S to ℤ_+ ∪ {∞}, satisfying some natural monotonicity conditions, but essentially describing the allowed drawings and how we want to count the crossings in them. Then deciding whether an input graph G has an allowed drawing D on S with κ(D) ≤ r can be done in time quadratic in the size of G (and exponential in other parameters). More generally, we may take as input an edge-colored graph, and distinguish crossings by the colors of the involved edges; and we may allow to perform a bounded number of edge removals and vertex splits to G before drawing it. The proof is a reduction to the embeddability of a graph on a two-dimensional simplicial complex. This framework implies, in a unified way, quadratic FPT algorithms for many topological crossing number variants established in the graph drawing community. Some of these variants already had previously published FPT algorithms, mostly relying on Courcelle’s metatheorem, but for many of those, we obtain an algorithm with a better runtime. Moreover, our framework extends, at no cost, to these crossing number variants in any fixed surface.
Cite as

Éric Colin de Verdière and Petr Hliněný. A Unified FPT Framework for Crossing Number Problems. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{colindeverdiere_et_al:LIPIcs.ESA.2025.21,
  author =	{Colin de Verdi\`{e}re, \'{E}ric and Hlin\v{e}n\'{y}, Petr},
  title =	{{A Unified FPT Framework for Crossing Number Problems}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.21},
  URN =		{urn:nbn:de:0030-drops-244897},
  doi =		{10.4230/LIPIcs.ESA.2025.21},
  annote =	{Keywords: computational geometry, fixed-parameter tractability, graph drawing, graph embedding, crossing number, two-dimensional simplicial complex, surface}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.8
Tight Bounds on the Number of Closest Pairs in Vertical Slabs

Authors: Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung, Jean-Lou De Carufel, John Iacono, Anil Maheshwari, Saeed Odak, Michiel Smid, and Csaba D. Tóth

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Let S be a set of n points in ℝ^d, where d ≥ 2 is a constant, and let H₁,H₂,…,H_{m+1} be a sequence of vertical hyperplanes that are sorted by their first coordinates, such that exactly n/m points of S are between any two successive hyperplanes. Let |A(S,m)| be the number of different closest pairs in the {(m+1) choose 2} vertical slabs that are bounded by H_i and H_j, over all 1 ≤ i < j ≤ m+1. We prove tight bounds for the largest possible value of |A(S,m)|, over all point sets of size n, and for all values of 1 ≤ m ≤ n. As a result of these bounds, we obtain, for any constant ε > 0, a data structure of size O(n), such that for any vertical query slab Q, the closest pair in the set Q ∩ S can be reported in O(n^{1/2+ε}) time. Prior to this work, no linear space data structure with sublinear query time was known.
Cite as

Ahmad Biniaz, Prosenjit Bose, Chaeyoon Chung, Jean-Lou De Carufel, John Iacono, Anil Maheshwari, Saeed Odak, Michiel Smid, and Csaba D. Tóth. Tight Bounds on the Number of Closest Pairs in Vertical Slabs. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{biniaz_et_al:LIPIcs.WADS.2025.8,
  author =	{Biniaz, Ahmad and Bose, Prosenjit and Chung, Chaeyoon and De Carufel, Jean-Lou and Iacono, John and Maheshwari, Anil and Odak, Saeed and Smid, Michiel and T\'{o}th, Csaba D.},
  title =	{{Tight Bounds on the Number of Closest Pairs in Vertical Slabs}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{8:1--8:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.8},
  URN =		{urn:nbn:de:0030-drops-242391},
  doi =		{10.4230/LIPIcs.WADS.2025.8},
  annote =	{Keywords: closest pair, vertical slab, data structure}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.17
Robust Contraction Decomposition for Minor-Free Graphs and Its Applications

Authors: Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Dániel Marx, Pranabendu Misra, Daniel Neuen, Saket Saurabh, Prafullkumar Tale, and Jie Xue

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We prove a robust contraction decomposition theorem for H-minor-free graphs, which states that given an H-minor-free graph G and an integer p, one can partition in polynomial time the vertices of G into p sets Z₁,… ,Z_p such that tw(G/(Z_i ⧵ Z')) = O(p + |Z'|) for all i ∈ [p] and Z' ⊆ Z_i. Here, tw(⋅) denotes the treewidth of a graph and G/(Z_i ⧵ Z') denotes the graph obtained from G by contracting all edges with both endpoints in Z_i ⧵ Z'. Our result generalizes earlier results by Klein [SICOMP 2008] and Demaine et al. [STOC 2011] based on partitioning E(G), and some recent theorems for planar graphs by Marx et al. [SODA 2022], for bounded-genus graphs (more generally, almost-embeddable graphs) by Bandyapadhyay et al. [SODA 2022], and for unit-disk graphs by Bandyapadhyay et al. [SoCG 2022]. The robust contraction decomposition theorem directly results in parameterized algorithms with running time 2^{Õ(√k)} ⋅ n^{O(1)} or n^{O(√k)} for every vertex/edge deletion problems on H-minor-free graphs that can be formulated as Permutation CSP Deletion or 2-Conn Permutation CSP Deletion. Consequently, we obtain the first subexponential-time parameterized algorithms for Subset Feedback Vertex Set, Subset Odd Cycle Transversal, Subset Group Feedback Vertex Set, 2-Conn Component Order Connectivity on H-minor-free graphs. For other problems which already have subexponential-time parameterized algorithms on H-minor-free graphs (e.g., Odd Cycle Transversal, Vertex Multiway Cut, Vertex Multicut, etc.), our theorem gives much simpler algorithms of the same running time.
Cite as

Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov, Dániel Marx, Pranabendu Misra, Daniel Neuen, Saket Saurabh, Prafullkumar Tale, and Jie Xue. Robust Contraction Decomposition for Minor-Free Graphs and Its Applications. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.ICALP.2025.17,
  author =	{Bandyapadhyay, Sayan and Lochet, William and Lokshtanov, Daniel and Marx, D\'{a}niel and Misra, Pranabendu and Neuen, Daniel and Saurabh, Saket and Tale, Prafullkumar and Xue, Jie},
  title =	{{Robust Contraction Decomposition for Minor-Free Graphs and Its Applications}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{17:1--17:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.17},
  URN =		{urn:nbn:de:0030-drops-233948},
  doi =		{10.4230/LIPIcs.ICALP.2025.17},
  annote =	{Keywords: subexponential time algorithms, graph decomposition, planar graphs, minor-free graphs, graph contraction}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.26
Pushing the Frontiers of Subexponential FPT Time for Feedback Vertex Set

Authors: Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
The paper deals with the Feedback Vertex Set problem parameterized by the solution size. Given a graph G and a parameter k, one has to decide if there is a set S of at most k vertices such that G-S is acyclic. Assuming the Exponential Time Hypothesis, it is known that FVS cannot be solved in time 2^{o(k)}n^{𝒪(1)} in general graphs. To overcome this, many recent results considered FVS restricted to particular intersection graph classes and provided such 2^{o(k)}n^{𝒪(1)} algorithms. In this paper we provide generic conditions on a graph class for the existence of an algorithm solving FVS in subexponential FPT time, i.e. time 2^k^ε poly(n), for some ε < 1, where n denotes the number of vertices of the instance and k the parameter. On the one hand this result unifies algorithms that have been proposed over the years for several graph classes such as planar graphs, map graphs, unit-disk graphs, pseudo-disk graphs, and string graphs of bounded edge-degree. On the other hand it extends the tractability horizon of FVS to new classes that are not amenable to previously used techniques, in particular intersection graphs of "thin" objects like segment graphs or more generally s-string graphs.
Cite as

Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond. Pushing the Frontiers of Subexponential FPT Time for Feedback Vertex Set. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{berthe_et_al:LIPIcs.ICALP.2025.26,
  author =	{Berthe, Ga\'{e}tan and Bougeret, Marin and Gon\c{c}alves, Daniel and Raymond, Jean-Florent},
  title =	{{Pushing the Frontiers of Subexponential FPT Time for Feedback Vertex Set}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.26},
  URN =		{urn:nbn:de:0030-drops-234036},
  doi =		{10.4230/LIPIcs.ICALP.2025.26},
  annote =	{Keywords: Subexponential FPT algorithms, geometric intersection graphs}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2025.35
Chain of Grounded Objectives: Concise Goal-Oriented Prompting for Code Generation

Authors: Sangyeop Yeo, Seung-Won Hwang, and Yu-Seung Ma

Published in: LIPIcs, Volume 333, 39th European Conference on Object-Oriented Programming (ECOOP 2025)

Abstract
The use of Large Language Models (LLMs) for code generation has gained significant attention in recent years. Existing methods often aim to improve the quality of generated code by incorporating additional contextual information or guidance into input prompts. Many of these approaches adopt process-oriented reasoning strategies, mimicking human-like step-by-step thinking; however, they may not always align with the structured nature of programming languages. This paper introduces Chain of Grounded Objectives (CGO), a concise goal-oriented prompting approach that embeds functional objectives into prompts to enhance code generation. By focusing on precisely defined objectives rather than explicit procedural steps, CGO aligns more naturally with programming tasks while retaining flexibility. Empirical evaluations on HumanEval, MBPP, their extended versions, and LiveCodeBench show that CGO achieves accuracy comparable to or better than existing methods while using fewer tokens, making it a more efficient approach to LLM-based code generation.
Cite as

Sangyeop Yeo, Seung-Won Hwang, and Yu-Seung Ma. Chain of Grounded Objectives: Concise Goal-Oriented Prompting for Code Generation. In 39th European Conference on Object-Oriented Programming (ECOOP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 333, pp. 35:1-35:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{yeo_et_al:LIPIcs.ECOOP.2025.35,
  author =	{Yeo, Sangyeop and Hwang, Seung-Won and Ma, Yu-Seung},
  title =	{{Chain of Grounded Objectives: Concise Goal-Oriented Prompting for Code Generation}},
  booktitle =	{39th European Conference on Object-Oriented Programming (ECOOP 2025)},
  pages =	{35:1--35:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-373-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{333},
  editor =	{Aldrich, Jonathan and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2025.35},
  URN =		{urn:nbn:de:0030-drops-233271},
  doi =		{10.4230/LIPIcs.ECOOP.2025.35},
  annote =	{Keywords: Artificial Intelligence, Natural Language Processing, Prompt Design, Large Language Models, Code Generation}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2025.23
Wastrumentation: Portable WebAssembly Dynamic Analysis with Support for Intercession

Authors: Aäron Munsters, Angel Luis Scull Pupo, and Elisa Gonzalez Boix

Published in: LIPIcs, Volume 333, 39th European Conference on Object-Oriented Programming (ECOOP 2025)

Abstract
Dynamic program analyses help in understanding a program’s runtime behavior and detect issues related to security, program comprehension, or profiling. Instrumentation platforms aid analysis developers by offering a high-level API to write the analysis, and inserting the analysis into the target program. However, current instrumentation platforms for WebAssembly (Wasm) restrict analysis portability because they require concrete runtime environments. Moreover, their analysis API only allows the development of analyses that observe the target program but cannot modify it. As a result, many popular dynamic analyses present for other languages, such as runtime hardening, virtual patching or runtime optimization, cannot currently be implemented for Wasm atop a dynamic analysis platform. Instead, they need to be built manually, which requires knowledge of low-level details of the Wasm’s semantics and instruction set, and how to safely manipulate it. This paper introduces Wastrumentation, the first dynamic analysis platform for WebAssembly that supports intercession. Our solution, based on source code instrumentation, weaves the analysis code directly into the target program code. Inlining the analysis into the target’s source code avoids dependencies on the runtime environment, making analyses portable across Wasm VMs. Moreover, it enables the implementation of analyses in any Wasm-compatible language. We evaluate our solution in two ways. First, we compare it against a state-of-the-art source code instrumentation platform using the WasmR3 benchmarks. The results show improved memory consumption and competitive performance overhead. Second, we develop an extensive portfolio of dynamic analyses, including novel analyses previously unattainable with source code instrumentation platforms, such as memoization, safe heap access, and the removal of NaN non-determinism.
Cite as

Aäron Munsters, Angel Luis Scull Pupo, and Elisa Gonzalez Boix. Wastrumentation: Portable WebAssembly Dynamic Analysis with Support for Intercession. In 39th European Conference on Object-Oriented Programming (ECOOP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 333, pp. 23:1-23:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{munsters_et_al:LIPIcs.ECOOP.2025.23,
  author =	{Munsters, A\"{a}ron and Scull Pupo, Angel Luis and Gonzalez Boix, Elisa},
  title =	{{Wastrumentation: Portable WebAssembly Dynamic Analysis with Support for Intercession}},
  booktitle =	{39th European Conference on Object-Oriented Programming (ECOOP 2025)},
  pages =	{23:1--23:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-373-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{333},
  editor =	{Aldrich, Jonathan and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2025.23},
  URN =		{urn:nbn:de:0030-drops-233153},
  doi =		{10.4230/LIPIcs.ECOOP.2025.23},
  annote =	{Keywords: WebAssembly, dynamic analysis, instrumentation platform, intercession}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.24
An 11/6-Approximation Algorithm for Vertex Cover on String Graphs

Authors: Édouard Bonnet and Paweł Rzążewski

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We present a 1.8334-approximation algorithm for Vertex Cover on string graphs given with a representation, which takes polynomial time in the size of the representation; the exact approximation factor is 11/6. Recently, the barrier of 2 was broken by Lokshtanov, Panolan, Saurabh, Xue, and Zehavi [SoGC '24] with a 1.9999-approximation algorithm. Thus we increase by three orders of magnitude the distance of the approximation ratio to the trivial bound of 2. Our algorithm is very simple. The intricacies reside in its analysis, where we mainly establish that string graphs without odd cycles of length at most 11 are 8-colorable. Previously, Chudnovsky, Scott, and Seymour [JCTB '21] showed that string graphs without odd cycles of length at most 7 are 80-colorable, and string graphs without odd cycles of length at most 5 have bounded chromatic number.
Cite as

Édouard Bonnet and Paweł Rzążewski. An 11/6-Approximation Algorithm for Vertex Cover on String Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.SoCG.2025.24,
  author =	{Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}},
  title =	{{An 11/6-Approximation Algorithm for Vertex Cover on String Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.24},
  URN =		{urn:nbn:de:0030-drops-231764},
  doi =		{10.4230/LIPIcs.SoCG.2025.24},
  annote =	{Keywords: Approximation algorithms, string graphs, Vertex Cover, Coloring, odd girth}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.32
Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-And-Bifurcate Technique

Authors: Timothy M. Chan and Zhengcheng Huang

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
In a series of papers, Avraham, Filtser, Kaplan, Katz, and Sharir (SoCG'14), Kaplan, Katz, Saban, and Sharir (ESA'23), and Katz, Saban, and Sharir (ESA'24) studied a class of geometric optimization problems - including reverse shortest path in unweighted and weighted unit-disk graphs, discrete Fréchet distance with one-sided shortcuts, and reverse shortest path in visibility graphs on 1.5-dimensional terrains - for which standard parametric search does not work well due to a lack of efficient parallel algorithms for the corresponding decision problems. The best currently known algorithms for all the above problems run in O^*(n^{6/5}) = O^*(n^{1.2}) time (ignoring subpolynomial factors), and they were obtained using a technique called shrink-and-bifurcate. We improve the running time to Õ(n^{8/7}) ≈ O(n^{1.143}) for these problems. Furthermore, specifically for reverse shortest path in unweighted unit-disk graphs, we improve the running time further to Õ(n^{9/8}) = Õ(n^{1.125}).
Cite as

Timothy M. Chan and Zhengcheng Huang. Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-And-Bifurcate Technique. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.SoCG.2025.32,
  author =	{Chan, Timothy M. and Huang, Zhengcheng},
  title =	{{Faster Algorithms for Reverse Shortest Path in Unit-Disk Graphs and Related Geometric Optimization Problems: Improving the Shrink-And-Bifurcate Technique}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{32:1--32:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.32},
  URN =		{urn:nbn:de:0030-drops-231845},
  doi =		{10.4230/LIPIcs.SoCG.2025.32},
  annote =	{Keywords: Geometric optimization problems, parametric search, shortest path, disk graphs, Fr\'{e}chet distance, visibility, distance selection, randomized algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.53
A PTAS for TSP with Neighbourhoods over Parallel Line Segments

Authors: Benyamin Ghaseminia and Mohammad R. Salavatipour

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We consider the Travelling Salesman Problem with Neighbourhoods (TSPN) on the Euclidean plane (ℝ²) and present a Polynomial-Time Approximation Scheme (PTAS) when the neighbourhoods are parallel line segments with lengths between [1, λ] for any constant value λ ≥ 1. In TSPN (which generalizes classic TSP), each client represents a set (or neighbourhood) of points in a metric and the goal is to find a minimum cost TSP tour that visits at least one point from each client set. In the Euclidean setting, each neighbourhood is a region on the plane. TSPN is significantly more difficult than classic TSP even in the Euclidean setting, as it captures group TSP. A notable case of TSPN is when each neighbourhood is a line segment. Although there are PTASs for when neighbourhoods are fat objects (with limited overlap), TSPN over line segments is APX-hard even if all the line segments have unit length. For parallel (unit) line segments, the best approximation factor is 3√2 from more than two decades ago. The PTAS we present in this paper settles the approximability of this case of the problem. Our algorithm finds a (1 + ε)-factor approximation for an instance of the problem for n segments with lengths in [1,λ] in time n^O(λ/ε³).
Cite as

Benyamin Ghaseminia and Mohammad R. Salavatipour. A PTAS for TSP with Neighbourhoods over Parallel Line Segments. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 53:1-53:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ghaseminia_et_al:LIPIcs.SoCG.2025.53,
  author =	{Ghaseminia, Benyamin and Salavatipour, Mohammad R.},
  title =	{{A PTAS for TSP with Neighbourhoods over Parallel Line Segments}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{53:1--53:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.53},
  URN =		{urn:nbn:de:0030-drops-232058},
  doi =		{10.4230/LIPIcs.SoCG.2025.53},
  annote =	{Keywords: Approximation Scheme, TSP Neighbourhood, Parallel line segments}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.7
Single-Source Shortest Path Problem in Weighted Disk Graphs

Authors: Shinwoo An, Eunjin Oh, and Jie Xue

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
In this paper, we present efficient algorithms for the single-source shortest path problem in weighted disk graphs. A disk graph is the intersection graph of a family of disks in the plane. Here, the weight of an edge is defined as the Euclidean distance between the centers of the disks corresponding to the endpoints of the edge. Given a family of n disks in the plane whose radii lie in [1,Ψ] and a source disk, we can compute a shortest path tree from a source vertex in the weighted disk graph in O(nlog² n log Ψ) time. Moreover, in the case that the radii of disks are arbitrarily large, we can compute a shortest path tree from a source vertex in the weighted disk graph in O(nlog⁴ n) time. This improves the best-known algorithm running in O(nlog⁶ n) time presented in ESA'23.
Cite as

Shinwoo An, Eunjin Oh, and Jie Xue. Single-Source Shortest Path Problem in Weighted Disk Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{an_et_al:LIPIcs.SoCG.2025.7,
  author =	{An, Shinwoo and Oh, Eunjin and Xue, Jie},
  title =	{{Single-Source Shortest Path Problem in Weighted Disk Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.7},
  URN =		{urn:nbn:de:0030-drops-231594},
  doi =		{10.4230/LIPIcs.SoCG.2025.7},
  annote =	{Keywords: Disk graphs, shortest path problem, compressed quadtrees}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.63
The Maximum Clique Problem in a Disk Graph Made Easy

Authors: J. Mark Keil and Debajyoti Mondal

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
A disk graph is an intersection graph of disks in ℝ². Determining the computational complexity of finding a maximum clique in a disk graph is a long-standing open problem. In 1990, Clark, Colbourn, and Johnson gave a polynomial-time algorithm for computing a maximum clique in a unit disk graph. However, finding a maximum clique when disks are of arbitrary size is widely believed to be a challenging open problem. In this paper, we provide a new perspective to examine adjacencies in a disk graph that helps obtain the following results. - We design an 𝒪^*(n^{2k})-time algorithm, where 𝒪^* hides a polynomial factor, to find a maximum clique in a n-vertex disk graph with k different sizes of radii. This is polynomial for every fixed k, and thus settles the open question for the case when k = 2. - Given a set of n unit disks, we show how to compute a maximum clique inside each possible axis-aligned rectangle determined by the disk centers in O(n⁵log n)-time. This is at least a factor of n^{4/3} faster than applying the fastest known algorithm for finding a maximum clique in a unit disk graph for each rectangle independently. - We give an 𝒪^*(n^{2rk})-time algorithm to find a maximum clique in a n-vertex ball graph with k different sizes of radii where the ball centers lie on r parallel planes. This is polynomial for every fixed k and r, and thus contrasts the previously known NP-hardness result for finding a maximum clique in an arbitrary ball graph. - We design an 𝒪^*(n^{2k})-time algorithm to find a maximum clique in the intersection graph of a set S of n L-visible convex polygons, where k is the number of distinct shapes in S. This contrasts the known hardness result on finding a maximum clique in the intersection graph of unit disks and axis-aligned rectangles.
Cite as

J. Mark Keil and Debajyoti Mondal. The Maximum Clique Problem in a Disk Graph Made Easy. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 63:1-63:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{keil_et_al:LIPIcs.SoCG.2025.63,
  author =	{Keil, J. Mark and Mondal, Debajyoti},
  title =	{{The Maximum Clique Problem in a Disk Graph Made Easy}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{63:1--63:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.63},
  URN =		{urn:nbn:de:0030-drops-232155},
  doi =		{10.4230/LIPIcs.SoCG.2025.63},
  annote =	{Keywords: Geometric Intersection Graphs, Disk Graphs, Ball Graphs, Maximum Clique}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.18
Finding a Shortest Curve That Separates Few Objects from Many

Authors: Therese Biedl, Éric Colin de Verdière, Fabrizio Frati, Anna Lubiw, and Günter Rote

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We present a fixed-parameter tractable (FPT) algorithm to find a shortest curve that encloses a set of k required objects in the plane while paying a penalty for enclosing unwanted objects. The input is a set of interior-disjoint simple polygons in the plane, where k of the polygons are required to be enclosed and the remaining optional polygons have non-negative penalties. The goal is to find a closed curve that is disjoint from the polygon interiors and encloses the k required polygons, while minimizing the length of the curve plus the penalties of the enclosed optional polygons. If the penalties are high, the output is a shortest curve that separates the required polygons from the others. The problem is NP-hard if k is not fixed, even in very special cases. The runtime of our algorithm is O(3^k n³), where n is the number of vertices of the input polygons. We extend the result to a graph version of the problem where the input is a connected plane graph with positive edge weights. There are k required faces; the remaining faces are optional and have non-negative penalties. The goal is to find a closed walk in the graph that encloses the k required faces, while minimizing the weight of the walk plus the penalties of the enclosed optional faces. We also consider an inverted version of the problem where the required objects must lie outside the curve. Our algorithms solve some other well-studied problems, such as geometric knapsack.
Cite as

Therese Biedl, Éric Colin de Verdière, Fabrizio Frati, Anna Lubiw, and Günter Rote. Finding a Shortest Curve That Separates Few Objects from Many. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{biedl_et_al:LIPIcs.SoCG.2025.18,
  author =	{Biedl, Therese and Colin de Verdi\`{e}re, \'{E}ric and Frati, Fabrizio and Lubiw, Anna and Rote, G\"{u}nter},
  title =	{{Finding a Shortest Curve That Separates Few Objects from Many}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.18},
  URN =		{urn:nbn:de:0030-drops-231701},
  doi =		{10.4230/LIPIcs.SoCG.2025.18},
  annote =	{Keywords: Enclosure, curve, separation, weakly simple polygon, Euler tour}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.73
Embedding Graphs as Euclidean kNN-Graphs

Authors: Thomas Schibler, Subhash Suri, and Jie Xue

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Let G = (V,E) be a directed graph on n vertices where each vertex has out-degree k. We say that G is kNN-realizable in d-dimensional Euclidean space if there exists a point set P = {p_1, p_2, …, p_n} in ℝ^d along with a one-to-one mapping ϕ: V → P such that for any u,v ∈ V, u is an out-neighbor of v in G if and only if ϕ(u) is one of the k nearest neighbors of ϕ(v); we call the map ϕ a kNN-realization of G in ℝ^d. The kNN-realization problem, which aims to compute a kNN-realization of an input graph in ℝ^d, is known to be NP-hard already for d = 2 and k = 1 [Eades and Whitesides, Theoretical Computer Science, 1996], and to the best of our knowledge has not been studied in dimension d = 1. The main results of this paper are the following: - For any fixed dimension d ≥ 2, we can efficiently compute an embedding realizing at least a 1 - ε fraction of G’s edges, or conclude that G is not kNN-realizable in ℝ^d. - For d = 1, we can decide in O(kn) time whether G is kNN-realizable and, if so, compute a realization in O(n^{2.5} poly(log n)) time.
Cite as

Thomas Schibler, Subhash Suri, and Jie Xue. Embedding Graphs as Euclidean kNN-Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 73:1-73:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schibler_et_al:LIPIcs.SoCG.2025.73,
  author =	{Schibler, Thomas and Suri, Subhash and Xue, Jie},
  title =	{{Embedding Graphs as Euclidean kNN-Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{73:1--73:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.73},
  URN =		{urn:nbn:de:0030-drops-232253},
  doi =		{10.4230/LIPIcs.SoCG.2025.73},
  annote =	{Keywords: Geometric graphs, k-nearest neighbors, graph embedding, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.77
Dynamic Maximum Depth of Geometric Objects

Authors: Subhash Suri, Jie Xue, Xiongxin Yang, and Jiumu Zhu

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Given a set of geometric objects in the plane (rectangles, squares, disks etc.), its maximum depth (or geometric clique) is the largest number of objects with a common intersection. In this paper, we present data structures for dynamically maintaining the maximum depth under insertions and deletions of geometric objects, with sublinear update time. We achieve the following results: - a 1/k-approximate dynamic maximum-depth data structure for (axis-parallel) rectangles with O(n^{1/(k+1)} log n) amortized update time, for any fixed k ∈ ℤ^+. In particular, when k = 1, this gives an exact data structure for rectangles with O(√n log n) amortized update time, almost matching the best known bound for the offline version of the problem. - a (1/2-ε)-approximate dynamic maximum-depth data structure for disks with n^{2/3} log^{O(1)}n amortized update time, for any constant ε > 0. Having exact data structures for disks with sublinear update time is unlikely, since the static maximum-depth problem for disks is 3SUM-hard and thus does not admit subquadratic-time algorithms.
Cite as

Subhash Suri, Jie Xue, Xiongxin Yang, and Jiumu Zhu. Dynamic Maximum Depth of Geometric Objects. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 77:1-77:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{suri_et_al:LIPIcs.SoCG.2025.77,
  author =	{Suri, Subhash and Xue, Jie and Yang, Xiongxin and Zhu, Jiumu},
  title =	{{Dynamic Maximum Depth of Geometric Objects}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{77:1--77:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.77},
  URN =		{urn:nbn:de:0030-drops-232295},
  doi =		{10.4230/LIPIcs.SoCG.2025.77},
  annote =	{Keywords: dynamic algorithms, maximum depth}
}
  • Refine by Type
  • 41 Document/PDF
  • 23 Document/HTML

  • Refine by Publication Year
  • 21 2025
  • 7 2024
  • 4 2023
  • 2 2022
  • 2 2021
  • Show More...

  • Refine by Author
  • 22 Xue, Jie
  • 8 Saurabh, Saket
  • 7 Lokshtanov, Daniel
  • 7 Suri, Subhash
  • 6 Wang, Haitao
  • Show More...

  • Refine by Series/Journal
  • 38 LIPIcs
  • 1 OASIcs
  • 2 TGDK

  • Refine by Classification
  • 20 Theory of computation → Computational geometry
  • 15 Theory of computation → Design and analysis of algorithms
  • 4 Theory of computation → Parameterized complexity and exact algorithms
  • 3 Theory of computation → Fixed parameter tractability
  • 2 Computing methodologies → Artificial intelligence
  • Show More...

  • Refine by Keyword
  • 6 approximation algorithms
  • 4 geometric intersection graphs
  • 3 Large Language Models
  • 3 geometric optimization
  • 2 Parameterized algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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