25 Search Results for "Megiddo, Nimrod"

Document
DOI: 10.4230/LIPIcs.STACS.2026.13
Line Cover and Related Problems

Authors: Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We study several extensions of the classic Line Cover problem of covering a set of n points in the plane with k lines. Line Cover is known to be NP-hard and our focus is on two natural generalizations: (1) Line Clustering, where the objective is to find k lines in the plane that minimize the sum of squares of distances of a given set of input points to the closest line, and (2) Hyperplane Cover, where the goal is to cover n points in ℝ^d by k hyperplanes. We also consider the more general Projective Clustering problem, which unifies both of these and has numerous applications in machine learning, data mining, and computational geometry. In this problem one seeks k affine subspaces of dimension r minimizing the sum of squares of distances of a given set of n points in ℝ^d to the closest point within one of the k affine subspaces. Our main contributions reveal interesting differences in the parameterized complexity of these problems. While Line Cover is fixed-parameter tractable parameterized by the number k of lines in the solution, we show that Line Clustering is W[1]-hard when parameterized by k and rule out algorithms of running time n^{o(k)} under the Exponential Time Hypothesis. Hyperplane Cover is known to be NP-hard even when d = 2 and by the work of Langerman and Morin [Discrete & Computational Geometry, 2005], it is FPT parameterized by k and d. We complement this result by establishing that Hyperplane Cover is W[2]-hard when parameterized by only k. We complement our hardness results by presenting an algorithm for Projective Clustering. We show that this problem is solvable in n^{𝒪(dk(r+1))} time. Not only does this yield an upper bound for Line Clustering that asymptotically matches our lower bound, but it also significantly extends the seminal work on k-Means Clustering (the special case r = 0) by Inaba, Katoh, and Imai [SoCG 1994].
Cite as

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach, Souvik Saha, Sanjay Seetharaman, and Anannya Upasana. Line Cover and Related Problems. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.STACS.2026.13,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Golovach, Petr A. and Saha, Souvik and Seetharaman, Sanjay and Upasana, Anannya},
  title =	{{Line Cover and Related Problems}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.13},
  URN =		{urn:nbn:de:0030-drops-255023},
  doi =		{10.4230/LIPIcs.STACS.2026.13},
  annote =	{Keywords: Point Line Cover, Projective Clustering, W-hardness, XP algorithm}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.53
Maximum Reachability Orientation of Mixed Graphs

Authors: Florian Hörsch

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We aim to find orientations of mixed graphs optimizing the total reachability, a problem that has applications in causality and biology. For given a digraph D, we use P(D) for the set of ordered pairs of distinct vertices in V(D) and we define κ_D:P(D) → {0,1} by κ_D(u,v) = 1 if v is reachable from u in D, and κ_D(u,v) = 0, otherwise. We use R(D) = ∑_{(u,v) ∈ P(D)}κ_D(u,v). Now, given a mixed graph G, we aim to find an orientation x⃑{G} of G that maximizes R(x⃑{G}). Hakimi, Schmeichel, and Young proved that the problem can be solved in polynomial time when restricted to undirected inputs. They inquired about the complexity in mixed graphs. We answer this question by showing that this problem is NP-hard, and, moreover, APX-hard. We then develop a finer understanding of how quickly the problem becomes difficult when going from undirected to mixed graphs. To this end, we consider the parameterized complexity of the problem with respect to the number k of preoriented arcs of G, a poorly studied form of parameterization. We show that the problem can be solved in time n^{O(k)} and that a (1-ε)-approximation can be computed in time f(k,ε)n^{O(1)} for any ε > 0.
Cite as

Florian Hörsch. Maximum Reachability Orientation of Mixed Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 53:1-53:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{horsch:LIPIcs.STACS.2026.53,
  author =	{H\"{o}rsch, Florian},
  title =	{{Maximum Reachability Orientation of Mixed Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{53:1--53:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.53},
  URN =		{urn:nbn:de:0030-drops-255421},
  doi =		{10.4230/LIPIcs.STACS.2026.53},
  annote =	{Keywords: orientations, mixed graphs, reachability, parameterized complexity, approximation}
}
Document
DOI: 10.4230/LIPIcs.CSL.2026.14
Satisfiability in Łukasiewicz Logic and Its Unbounded Relative

Authors: Zuzana Haniková and Filip Jankovec

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract
Unbounded Łukasiewicz logic is a substructural logic that combines features of infinite-valued Łukasiewicz logic with those of abelian logic. The logic is finitely strongly complete w.r.t. the additive 𝓁-group on the reals expanded with a distinguished element -1. We show that the existential theory of this structure is NP-complete. This provides a complexity upper bound for the set of theorems and the finite consequence relation of unbounded Łukasiewicz logic. The result is obtained by reducing the problem to the existential theory of the MV-algebra on the reals, the standard semantics of Łukasiewicz logic. This provides a new connection between both logics. The result entails a translation of the existential theory of the standard MV-algebra into itself.
Cite as

Zuzana Haniková and Filip Jankovec. Satisfiability in Łukasiewicz Logic and Its Unbounded Relative. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hanikova_et_al:LIPIcs.CSL.2026.14,
  author =	{Hanikov\'{a}, Zuzana and Jankovec, Filip},
  title =	{{Satisfiability in {\L}ukasiewicz Logic and Its Unbounded Relative}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.14},
  URN =		{urn:nbn:de:0030-drops-254380},
  doi =		{10.4230/LIPIcs.CSL.2026.14},
  annote =	{Keywords: unbounded {\L}ukasiewicz Logic, {\L}ukasiewicz Logic, Abelian Logic, existential theory, computational complexity, NP-completeness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.7
An Unholy Trinity: TFNP, Polynomial Systems, and the Quantum Satisfiability Problem

Authors: Marco Aldi, Sevag Gharibian, and Dorian Rudolph

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intractable. Despite the success of the theory at showing intractability of problems such as computing Brouwer fixed points and Nash equilibria, subclasses of TFNP remain arguably few and far between. In this work, we define two new subclasses of TFNP borne of the study of complex polynomial systems: Multi-homogeneous Systems (MHS) and Sparse Fundamental Theorem of Algebra (SFTA). The first of these is based on Bézout’s theorem from algebraic geometry, marking the first TFNP subclass based on an algebraic geometric principle. At the heart of our study is the computational problem known as Quantum SAT (QSAT) with a System of Distinct Representatives (SDR), first studied by [Laumann, Läuchli, Moessner, Scardicchio, and Sondhi 2010]. Among other results, we show that QSAT with SDR is MHS-complete, thus giving not only the first link between quantum complexity theory and TFNP, but also the first TFNP problem whose classical variant (SAT with SDR) is easy but whose quantum variant is hard. We also show how to embed the roots of a sparse, high-degree, univariate polynomial into QSAT with SDR, obtaining that SFTA is contained in a zero-error version of MHS. We conjecture this construction also works in the low-error setting, which would imply SFTA ⊆ MHS.
Cite as

Marco Aldi, Sevag Gharibian, and Dorian Rudolph. An Unholy Trinity: TFNP, Polynomial Systems, and the Quantum Satisfiability Problem. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 7:1-7:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aldi_et_al:LIPIcs.ITCS.2026.7,
  author =	{Aldi, Marco and Gharibian, Sevag and Rudolph, Dorian},
  title =	{{An Unholy Trinity: TFNP, Polynomial Systems, and the Quantum Satisfiability Problem}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{7:1--7:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.7},
  URN =		{urn:nbn:de:0030-drops-252946},
  doi =		{10.4230/LIPIcs.ITCS.2026.7},
  annote =	{Keywords: quantum complexity theory, Quantum Merlin Arthur (QMA), Quantum Satisfiability Problem (QSAT), total function NP (TFNP)}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.8
Binary k-Center with Missing Entries: Structure Leads to Tractability

Authors: Tobias Friedrich, Kirill Simonov, and Farehe Soheil

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
k-Center clustering is a fundamental classification problem, where the task is to categorize the given collection of entities into k clusters and come up with a representative for each cluster, so that the maximum distance between an entity and its representative is minimized. In this work, we focus on the setting where the entities are represented by binary vectors with missing entries, which model incomplete categorical data. This version of the problem has wide applications, from predictive analytics to bioinformatics. Our main finding is that the problem, which is notoriously hard from the classical complexity viewpoint, becomes tractable as soon as the known entries are sparse and exhibit a certain structure. Formally, we show fixed-parameter tractable algorithms for the parameters vertex cover, fracture number, and treewidth of the row-column graph, which encodes the positions of the known entries of the matrix. Additionally, we tie the complexity of the 1-cluster variant of the problem, which is famous under the name Closest String, to the complexity of solving integer linear programs with few constraints. This implies, in particular, that improving upon the running times of our algorithms would lead to more efficient algorithms for integer linear programming in general.
Cite as

Tobias Friedrich, Kirill Simonov, and Farehe Soheil. Binary k-Center with Missing Entries: Structure Leads to Tractability. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{friedrich_et_al:LIPIcs.IPEC.2025.8,
  author =	{Friedrich, Tobias and Simonov, Kirill and Soheil, Farehe},
  title =	{{Binary k-Center with Missing Entries: Structure Leads to Tractability}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.8},
  URN =		{urn:nbn:de:0030-drops-251403},
  doi =		{10.4230/LIPIcs.IPEC.2025.8},
  annote =	{Keywords: Clustering, Missing Entries, k-Center, Parameterized Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.18
An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies

Authors: Yike Chen, Ke Shi, and Chao Xu

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The Stacker Crane Problem (SCP) is a variant of the Traveling Salesman Problem. In SCP, pairs of pickup and delivery points are designated on a graph, and a crane must visit these points to move objects from each pickup location to its respective delivery point. The goal is to minimize the total distance traveled. SCP is known to be NP-hard, even on trees. The only positive results, in terms of polynomial-time solvability, apply to graphs that are topologically equivalent to a path or a cycle. We propose an algorithm that is optimal for each fixed topology, running in near-linear time. This is achieved by demonstrating that the problem is fixed-parameter tractable (FPT) when parameterized by both the cycle rank and the number of branch vertices.
Cite as

Yike Chen, Ke Shi, and Chao Xu. An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 18:1-18:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ISAAC.2025.18,
  author =	{Chen, Yike and Shi, Ke and Xu, Chao},
  title =	{{An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{18:1--18:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.18},
  URN =		{urn:nbn:de:0030-drops-249269},
  doi =		{10.4230/LIPIcs.ISAAC.2025.18},
  annote =	{Keywords: Stacker Crane Problem, Fixed-Parameter Tractable, Min-Cost Circulation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.21
Covering Weighted Points Using Unit Squares

Authors: Chaeyoon Chung, Jaegun Lee, and Hee-Kap Ahn

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Given a set of n points in d-dimensional space, each assigned a positive weight, we study the problem of finding k axis-parallel unit hypercubes that maximize the total weight of the points contained in their union. In this paper, we present both exact and (1 - ε)-approximation algorithms for the case of k = 2. We present an exact algorithm that runs in O(n²) time in the plane, improving the previous O(n² log² n)-time result. This algorithm generalizes to higher dimensions and larger k in O(n^{dk/2}) time for fixed d and k. We also present a (1 - ε)-approximation algorithm that runs in O(n log min{n, 1/ε} + 1/ε³) time for k = 2 in the plane, improving the best known result. Our approximation algorithm also extends to higher dimensions.
Cite as

Chaeyoon Chung, Jaegun Lee, and Hee-Kap Ahn. Covering Weighted Points Using Unit Squares. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chung_et_al:LIPIcs.ISAAC.2025.21,
  author =	{Chung, Chaeyoon and Lee, Jaegun and Ahn, Hee-Kap},
  title =	{{Covering Weighted Points Using Unit Squares}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.21},
  URN =		{urn:nbn:de:0030-drops-249292},
  doi =		{10.4230/LIPIcs.ISAAC.2025.21},
  annote =	{Keywords: Maximum coverage, Unit squares, Approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.38
Structural Parameters for Steiner Orientation

Authors: Tesshu Hanaka, Michael Lampis, Nikolaos Melissinos, Edouard Nemery, Hirotaka Ono, and Manolis Vasilakis

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
We consider the Steiner Orientation problem, where we are given as input a mixed graph G = (V,E,A) and a set of k demand pairs (s_i,t_i), i ∈ [k]. The goal is to orient the undirected edges of G in a way that the resulting directed graph has a directed path from s_i to t_i for all i ∈ [k]. We adopt the point of view of structural parameterized complexity and investigate the complexity of Steiner Orientation for standard measures, such as treewidth. Our results indicate that Steiner Orientation is a surprisingly hard problem from this point of view. In particular, our main contributions are the following: 1) We show that Steiner Orientation is NP-complete on instances where the underlying graph has feedback vertex number 2, treewidth 2, pathwidth 3, and vertex integrity 6. 2) We present an XP algorithm parameterized by vertex cover number vc of complexity n^O(vc²). Furthermore, we show that this running time is essentially optimal by proving that a running time of n^o(vc²) would refute the ETH. 3) We consider parameterizations by the number of undirected or directed edges (|E| or |A|) and we observe that the trivial 2^|E| n^O(1)-time algorithm for the former parameter is optimal under the SETH. Complementing this, we show that the problem admits a 2^O(|A|) n^O(1)-time algorithm. In addition to the above, we consider the complexity of Steiner Orientation parameterized by tw+k (FPT), distance to clique (FPT), and vc+k (FPT with a polynomial kernel).
Cite as

Tesshu Hanaka, Michael Lampis, Nikolaos Melissinos, Edouard Nemery, Hirotaka Ono, and Manolis Vasilakis. Structural Parameters for Steiner Orientation. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.ISAAC.2025.38,
  author =	{Hanaka, Tesshu and Lampis, Michael and Melissinos, Nikolaos and Nemery, Edouard and Ono, Hirotaka and Vasilakis, Manolis},
  title =	{{Structural Parameters for Steiner Orientation}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.38},
  URN =		{urn:nbn:de:0030-drops-249461},
  doi =		{10.4230/LIPIcs.ISAAC.2025.38},
  annote =	{Keywords: ETH, Steiner Orientation, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.112
A Faster Parametric Search for the Integral Quickest Transshipment Problem

Authors: Mariia Anapolska, Dario van den Boom, Christina Büsing, and Timo Gersing

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

Abstract
Algorithms for computing fractional solutions to the quickest transshipment problem have been significantly improved since Hoppe and Tardos first solved the problem in strongly polynomial time. For integral solutions, however, no structural improvements on their algorithm itself have yet been proposed. Runtime improvements are limited to general progress on submodular function minimization (SFM), which is an integral part of Hoppe and Tardos' algorithm. In fact, SFM constitutes the main computational load of the algorithm, as the runtime is blown up by using it within Megiddo’s parametric search algorithm. We replace this part of Hoppe and Tardos' algorithm with a more efficient routine that solves only a linear number of SFM and, in contrast to previous techniques, exclusively uses minimum cost flow algorithms within Megiddo’s parametric search. Our approach improves the state-of-the-art runtime from 𝒪̃(m⁴ k^15) down to 𝒪̃(m²k⁵ + m⁴ k²), where k is the number of terminals and m is the number of arcs.
Cite as

Mariia Anapolska, Dario van den Boom, Christina Büsing, and Timo Gersing. A Faster Parametric Search for the Integral Quickest Transshipment Problem. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 112:1-112:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{anapolska_et_al:LIPIcs.ESA.2025.112,
  author =	{Anapolska, Mariia and van den Boom, Dario and B\"{u}sing, Christina and Gersing, Timo},
  title =	{{A Faster Parametric Search for the Integral Quickest Transshipment Problem}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{112:1--112:15},
  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.112},
  URN =		{urn:nbn:de:0030-drops-245817},
  doi =		{10.4230/LIPIcs.ESA.2025.112},
  annote =	{Keywords: Flow over time, dynamic transshipment, quickest transshipment, parametric submodular functions, efficient algorithms}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.50
Shared Randomness in Locally Checkable Problems: The Role of Computational Assumptions

Authors: Adar Hadad and Moni Naor

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
Shared randomness is a valuable resource in distributed computing, allowing some form of coordination between processors without explicit communication. But what happens when the shared random string can affect the inputs to the system? Consider the class of distributed graph problems where the correctness of solutions can be checked locally, known as Locally Checkable Labelings (LCL). LCL problems have been extensively studied in the LOCAL model, where nodes operate in synchronous rounds and have access only to local information. This has led to intriguing insights regarding the power of private randomness. E.g., for certain round complexity classes, derandomization does not incur an overhead (asymptotically). This work considers a setting where the randomness is public. Recently, an LCL problem for which shared randomness can reduce the round complexity was discovered by Balliu et al. (ICALP 2025). This result applies to inputs set obliviously of the shared randomness, which may not always be a plausible assumption. We define a model where the inputs can be adversarially chosen, even based on the shared randomness, which we now call preset public coins. We study LCL problems in the preset public coins model, under assumptions regarding the computational power of the adversary that selects the input. We show connections to hardness in the class TFNP. Our results are: 1) Assuming a hard-on-average problem in TFNP, we present an LCL problem that, in the preset public coins model, demonstrates a gap in the round complexity between polynomial-time and unbounded adversaries. 2) An LCL problem for which the error probability is significantly higher when facing unbounded adversaries implies a hard-on-average problem in TFNP/poly.
Cite as

Adar Hadad and Moni Naor. Shared Randomness in Locally Checkable Problems: The Role of Computational Assumptions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 50:1-50:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hadad_et_al:LIPIcs.APPROX/RANDOM.2025.50,
  author =	{Hadad, Adar and Naor, Moni},
  title =	{{Shared Randomness in Locally Checkable Problems: The Role of Computational Assumptions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{50:1--50:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.50},
  URN =		{urn:nbn:de:0030-drops-244161},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.50},
  annote =	{Keywords: Distributed Graph Algorithms, Common Random String, Cryptographic Hardness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.33
Hitting and Covering Affine Families of Convex Polyhedra, with Applications to Robust Optimization

Authors: Jean Cardinal, Xavier Goaoc, and Sarah Wajsbrot

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
Geometric hitting set problems, in which we seek a smallest set of points that collectively hit a given set of ranges, are ubiquitous in computational geometry. Most often, the set is discrete and is given explicitly. We propose new variants of these problems, dealing with continuous families of convex polyhedra, and show that they capture decision versions of the two-level finite adaptability problem in robust optimization. We show that these problems can be solved in strongly polynomial time when the size of the hitting/covering set and the dimension of the polyhedra and the parameter space are constant. We also show that the hitting set problem can be solved in strongly quadratic time for one-parameter families of convex polyhedra in constant dimension. This leads to new tractability results for finite adaptability that are the first ones with so-called left-hand-side uncertainty, where the underlying problem is non-linear.
Cite as

Jean Cardinal, Xavier Goaoc, and Sarah Wajsbrot. Hitting and Covering Affine Families of Convex Polyhedra, with Applications to Robust Optimization. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 33:1-33:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.MFCS.2025.33,
  author =	{Cardinal, Jean and Goaoc, Xavier and Wajsbrot, Sarah},
  title =	{{Hitting and Covering Affine Families of Convex Polyhedra, with Applications to Robust Optimization}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{33:1--33:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.33},
  URN =		{urn:nbn:de:0030-drops-241401},
  doi =		{10.4230/LIPIcs.MFCS.2025.33},
  annote =	{Keywords: Geometric hitting set problem, Continuous families of polyhedra, Robust optimization}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.43
The Complexity of Computing Second Solutions

Authors: Fabian Egidy, Christian Glaßer, and Fynn Godau

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We study the complexity of computing second solutions for NP search problems, i. e., given a problem instance x and a valid solution y, we have to find another valid solution y'. Our main result shows that for typical NP decision problems, the complexity of computing second solutions is completely determined by the choice of the type of solution (i. e., the specific function problem), but independent of the underlying decision problem. More precisely, we show that for every X ∈ NP that is 1-paddable (a weak form of paddability), different choices of the type of solution lead to different second solution problems, which altogether have the same degree structure as the entire class of NP search problems (FNP). In fact, each degree of difficulty within FNP does occur as a second solution problem for X. This proves that typical NP decision problems have no intrinsic complexity w. r. t. the search for a second solution, but only the specification of the type of solution determines this complexity. This explains the empirical observation that the difficulty of computing second solutions strongly depends on the formulation of the problem. Moreover, we show that the complexities of a search problem and its second solution variant are independent in the following sense: For all search problems A and B representing two degrees of difficulty, there exists a search problem C such that 1) C is as difficult as A and 2) computing second solutions for C is as difficult as B.
Cite as

Fabian Egidy, Christian Glaßer, and Fynn Godau. The Complexity of Computing Second Solutions. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{egidy_et_al:LIPIcs.MFCS.2025.43,
  author =	{Egidy, Fabian and Gla{\ss}er, Christian and Godau, Fynn},
  title =	{{The Complexity of Computing Second Solutions}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.43},
  URN =		{urn:nbn:de:0030-drops-241505},
  doi =		{10.4230/LIPIcs.MFCS.2025.43},
  annote =	{Keywords: function problems, another solution problem, turing machines}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.23
On the Instance Optimality of Detecting Collisions and Subgraphs

Authors: Omri Ben-Eliezer, Tomer Grossman, and Moni Naor

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

Abstract
Suppose you are given a function f: [n] → [n] via (black-box) query access to the function. You are looking to find something local, like a collision (a pair x ≠ y s.t. f(x) = f(y)). The question is whether knowing the "shape" of the function helps you or not (by shape we mean that some permutation of the function is known). Formally, we investigate the unlabeled instance optimality of substructure detection problems in graphs and functions. A problem is g(n)-instance optimal if it admits an algorithm A satisfying that for any possible input, the (randomized) query complexity of A is at most g(n) times larger than the query complexity of any algorithm A' which solves the same problem while holding an unlabeled copy of the input (i.e., any A' that "knows the structure of the input"). Our results point to a trichotomy of unlabeled instance optimality among substructure detection problems in graphs and functions: - A few very simple properties have an O(1)-instance optimal algorithm. - Most properties of graphs and functions, with examples such as containing a fixed point or a 3-collision in functions, or a triangle in graphs, are n^{c}-far from instance optimal for some constant c > 0. - The problems of collision detection in functions and finding a claw in a graph serve as a middle ground between the two regimes. We show that these two properties are not Ω(log n)-instance optimal, and conjecture that this bound is tight. We provide evidence towards this conjecture, by proving that finding a claw in a graph is O(log(n))-instance optimal among all input graphs for which the query complexity of an algorithm holding an unlabeled certificate is O(√{n/(log n)}).
Cite as

Omri Ben-Eliezer, Tomer Grossman, and Moni Naor. On the Instance Optimality of Detecting Collisions and Subgraphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{beneliezer_et_al:LIPIcs.ICALP.2025.23,
  author =	{Ben-Eliezer, Omri and Grossman, Tomer and Naor, Moni},
  title =	{{On the Instance Optimality of Detecting Collisions and Subgraphs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{23:1--23:14},
  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.23},
  URN =		{urn:nbn:de:0030-drops-234002},
  doi =		{10.4230/LIPIcs.ICALP.2025.23},
  annote =	{Keywords: instance optimality, instance complexity, unlabeled certificate, subgraph detection, collision detection}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.144
Probabilistic and Causal Satisfiability: Constraining the Model

Authors: Markus Bläser, Julian Dörfler, Maciej Liśkiewicz, and Benito van der Zander

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

Abstract
We study the complexity of satisfiability problems in probabilistic and causal reasoning. Given random variables X₁, X₂,… over finite domains, the basic terms are probabilities of propositional formulas over atomic events X_i = x_i, such as ℙ(X₁ = x₁) or ℙ(X₁ = x₁ ∨ X₂ = x₂). The basic terms can be combined using addition (yielding linear terms) or multiplication (polynomial terms). The probabilistic satisfiability problem asks whether a joint probability distribution satisfies a Boolean combination of (in)equalities over such terms. Fagin et al. [Fagin et al., 1990] showed that for basic and linear terms, this problem is NP-complete, making it no harder than Boolean satisfiability, while Mossé et al. [Mossé et al., 2022] proved that for polynomial terms, it is complete for the existential theory of the reals. Pearl’s Causal Hierarchy (PCH) extends the probabilistic setting with interventional and counterfactual reasoning, enriching the expressiveness of the languages. However, Mossé et al. [Mossé et al., 2022] found that the complexity of satisfiability remains unchanged. Van der Zander et al. [van der Zander et al., 2023] showed that introducing a marginalization operator to languages induces a significant increase in complexity. We extend this line of work by adding two new dimensions to the problem by constraining the models. First, we fix the graph structure of the underlying structural causal model, motivated by settings like Pearl’s do-calculus, and give a nearly complete landscape across different arithmetics and PCH levels. Second, we study small models. While earlier work showed that satisfiable instances admit polynomial-size models, this is no longer guaranteed with compact marginalization. We characterize the complexities of satisfiability under small-model constraints across different settings.
Cite as

Markus Bläser, Julian Dörfler, Maciej Liśkiewicz, and Benito van der Zander. Probabilistic and Causal Satisfiability: Constraining the Model. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 144:1-144:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blaser_et_al:LIPIcs.ICALP.2025.144,
  author =	{Bl\"{a}ser, Markus and D\"{o}rfler, Julian and Li\'{s}kiewicz, Maciej and van der Zander, Benito},
  title =	{{Probabilistic and Causal Satisfiability: Constraining the Model}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{144:1--144:20},
  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.144},
  URN =		{urn:nbn:de:0030-drops-235214},
  doi =		{10.4230/LIPIcs.ICALP.2025.144},
  annote =	{Keywords: Existential theory of the real numbers, Computational complexity, Probabilistic logic, Structural Causal Models}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.31
A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation

Authors: Timothy M. Chan and Isaac M. Hair

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

Abstract
Given two convex polygons P and Q with n and m edges, the maximum overlap problem is to find a translation of P that maximizes the area of its intersection with Q. We give the first randomized algorithm for this problem with linear running time. Our result improves the previous two-and-a-half-decades-old algorithm by de Berg, Cheong, Devillers, van Kreveld, and Teillaud (1998), which ran in O((n+m)log(n+m)) time, as well as multiple recent algorithms given for special cases of the problem.
Cite as

Timothy M. Chan and Isaac M. Hair. A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chan_et_al:LIPIcs.SoCG.2025.31,
  author =	{Chan, Timothy M. and Hair, Isaac M.},
  title =	{{A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{31:1--31: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.31},
  URN =		{urn:nbn:de:0030-drops-231832},
  doi =		{10.4230/LIPIcs.SoCG.2025.31},
  annote =	{Keywords: Convex polygons, shape matching, prune-and-search, parametric search}
}
  • Refine by Type
  • 25 Document/PDF
  • 21 Document/HTML

  • Refine by Publication Year
  • 4 2026
  • 17 2025
  • 1 2014
  • 3 2010

  • Refine by Author
  • 2 Chan, Timothy M.
  • 2 Megiddo, Nimrod
  • 2 Naor, Moni
  • 2 Vazirani, Vijay V.
  • 1 Ahn, Hee-Kap
  • Show More...

  • Refine by Series/Journal
  • 21 LIPIcs
  • 1 DagRep
  • 3 DagSemProc

  • Refine by Classification
  • 8 Theory of computation → Computational geometry
  • 4 Theory of computation → Fixed parameter tractability
  • 3 Theory of computation → Parameterized complexity and exact algorithms
  • 3 Theory of computation → Problems, reductions and completeness
  • 2 Theory of computation → Complexity classes
  • Show More...

  • Refine by Keyword
  • 2 Clustering
  • 2 Treewidth
  • 2 k-Center
  • 2 parametric search
  • 1 Abelian Logic
  • 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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact