116 Search Results for "Khanna, Sanjeev"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.44
Multiplicative Error Set System Sparsification: A Simpler Proof via Chain Length Contraction

Authors: Joshua Brakensiek, Venkatesan Guruswami, and Aaron Putterman

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
The chain length of a set family 𝒮 ⊆ 2^[m] is the largest ascending sequence of sets in containment order in the union-closure of S. In this work, we provide a significantly simpler and more optimal characterization of the sparsifiability of set systems in terms of their chain length, improving on the work of Brakensiek and Guruswami [STOC 2025]. Our proof relies on a generalization of Karger’s [SODA 1993] famous contraction algorithm and its recent linear algebraic extensions [Khanna-Putterman-Sudan SODA 2024], and our resulting bounds show that, just as VC dimension characterizes the additive sparsifiability of a set system, chain length governs the multiplicative sparsifiability. As a corollary, we obtain improved bounds for weighted CSP sparsification.
Cite as

Joshua Brakensiek, Venkatesan Guruswami, and Aaron Putterman. Multiplicative Error Set System Sparsification: A Simpler Proof via Chain Length Contraction. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 44:1-44:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brakensiek_et_al:LIPIcs.ICALP.2026.44,
  author =	{Brakensiek, Joshua and Guruswami, Venkatesan and Putterman, Aaron},
  title =	{{Multiplicative Error Set System Sparsification: A Simpler Proof via Chain Length Contraction}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{44:1--44:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael 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.2026.44},
  URN =		{urn:nbn:de:0030-drops-264331},
  doi =		{10.4230/LIPIcs.ICALP.2026.44},
  annote =	{Keywords: constraint satisfaction problem, chain length, sparsification, VC dimension}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.124
An Õ(n^{3/7}) Round Parallel Algorithm for Matroid Bases

Authors: Sanjeev Khanna, Aaron Putterman, and Junkai Song

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We study the parallel (adaptive) complexity of the classic problem of finding a basis in an n-element matroid, given access via an independence oracle. In this model, the algorithm may submit polynomially many independence queries in each round, and the central question is: how many rounds are necessary and sufficient to find a basis? Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988; hereafter KUW) initiated this study, showing that O(√n) adaptive rounds suffice for any matroid, and that Ω̃(n^{1/3}) rounds are necessary even for partition matroids. This left a substantial gap that persisted for nearly four decades, until Khanna, Putterman, and Song (FOCS 2025; hereafter KPS) achieved Õ(n^{7/15}) rounds, the first improvement since KUW. In this work, we make another conceptual advance beyond KPS, giving a new algorithm that finds a matroid basis in Õ(n^{3/7}) rounds. We develop a structural and algorithmic framework that brings a new lens to the analysis of random circuits, moving from reasoning about individual elements to understanding how dependencies span multiple elements simultaneously. Specifically, our framework introduces three new ideas: 1) A new subset-based decomposition that provides precise guarantees on how random circuits intersect groups of elements, yet remains computable in few adaptive rounds. 2) A new method for identifying and removing redundant elements in bulk, based on short circuit witnesses that certify redundancy across large portions of the matroid. 3) An adaptive early-stopping strategy that uses the evolving structure of the matroid to decide when to contract or delete, preventing wasted rounds. Each of these contributions, in isolation, already yields meaningful improvements over the round complexity achieved in KPS; their combination enables our main result of Õ(n^{3/7}) rounds. As further consequences, incorporating our improved basis-finding algorithm into known reductions yields an Õ(n^{17/21})-round parallel algorithm for matroid intersection, as well as an Õ(n^{3/7})-round parallel algorithm for approximate monotone submodular maximization under a matroid constraint.
Cite as

Sanjeev Khanna, Aaron Putterman, and Junkai Song. An Õ(n^{3/7}) Round Parallel Algorithm for Matroid Bases. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 124:1-124:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{khanna_et_al:LIPIcs.ICALP.2026.124,
  author =	{Khanna, Sanjeev and Putterman, Aaron and Song, Junkai},
  title =	{{An Õ(n^\{3/7\}) Round Parallel Algorithm for Matroid Bases}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{124:1--124:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael 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.2026.124},
  URN =		{urn:nbn:de:0030-drops-265130},
  doi =		{10.4230/LIPIcs.ICALP.2026.124},
  annote =	{Keywords: parallel algorithms, matroids}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2026.125
Optimal Parallel Basis Finding in Graphic and Related Matroids

Authors: Sanjeev Khanna, Aaron Putterman, and Junkai Song

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract
We study the parallel complexity of finding a basis of a graphic matroid under independence-oracle access. Karp, Upfal, and Wigderson (FOCS 1985, JCSS 1988) initiated the study of this problem and established two algorithms for finding a spanning forest: one running in O(log m) rounds with m^{Θ(log m)} queries, and another, for any d ∈ ℤ^+, running in O(m^{2/d}) rounds with Θ(m^d) queries. A key open question they posed was whether one could simultaneously achieve polylogarithmic rounds and polynomially many queries. We give a deterministic algorithm that uses O(log m) adaptive rounds and poly(m) non-adaptive queries per round to return a spanning forest on m edges, and complement this result with a matching Ω(log m) lower bound for any (even randomized) algorithm with poly(m) queries per round. Thus, the adaptive round complexity for graphic matroids is characterized exactly, settling this long-standing problem. Beyond graphs, we show that our framework also yields an O(log m)-round, poly(m)-query algorithm for any binary matroid satisfying a smooth circuit counting property, implying, among others, an optimal O(log m)-round parallel algorithms for finding bases of cographic matroids. Finally, we conjecture a natural strengthening of known circuit-counting bounds for the much broader class of regular matroids and even an extension to so-called max-flow min-cut matroids; assuming it, our algorithm achieves the same O(log m) rounds and poly(m) queries for all such matroids - which includes graphic and cographic matroids as special cases.
Cite as

Sanjeev Khanna, Aaron Putterman, and Junkai Song. Optimal Parallel Basis Finding in Graphic and Related Matroids. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 125:1-125:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{khanna_et_al:LIPIcs.ICALP.2026.125,
  author =	{Khanna, Sanjeev and Putterman, Aaron and Song, Junkai},
  title =	{{Optimal Parallel Basis Finding in Graphic and Related Matroids}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{125:1--125:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael 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.2026.125},
  URN =		{urn:nbn:de:0030-drops-265143},
  doi =		{10.4230/LIPIcs.ICALP.2026.125},
  annote =	{Keywords: parallel algorithms, matroids}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.8
General Multiplicative Spanners in Practice

Authors: Fritz Bökler, Markus Chimani, and Henning Jasper

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Given an undirected graph G with edge weights and lengths, a minimum α-spanner is a least-weight subgraph H ⊆ G that preserves distances w.r.t. the lengths between all node pairs up to a factor of α. Literature often takes the simplifying assumption of a single (coupled) edge function for weights and lengths. For such instances, several exact and non-exact algorithms are known and have been thoroughly evaluated in practice. However, many practical instances have decoupled form, as their weights and lengths are generally independent. Due to the increased complexity, only few (and even fewer practical) algorithms are able to guarantee low-weight solutions. This prompts practitioners to force their naturally decoupled instances into a coupled format, forsaking any quality guarantee. We implement several exact, approximative and heuristic algorithms for decoupled α-spanners, and use algorithm engineering to speed them up in practice. Our hypothesis-driven experiments evaluate their performance w.r.t. solution quality and speed. Generally, many practical instances can indeed be solved exactly within reasonable time, while LP-based approximation algorithms are not worthwhile. We find that standard greedy algorithms often yield acceptable results, but there are also practical instances for which they yield arbitrarily poor solutions. Here, augmented greedy variations offer a good compromise between solution quality and speed.
Cite as

Fritz Bökler, Markus Chimani, and Henning Jasper. General Multiplicative Spanners in Practice. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 8:1-8:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bokler_et_al:LIPIcs.SEA.2026.8,
  author =	{B\"{o}kler, Fritz and Chimani, Markus and Jasper, Henning},
  title =	{{General Multiplicative Spanners in Practice}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{8:1--8:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.8},
  URN =		{urn:nbn:de:0030-drops-260120},
  doi =		{10.4230/LIPIcs.SEA.2026.8},
  annote =	{Keywords: Graph spanners, ILP, experimental study, algorithm engineering}
}
Document
DOI: 10.4230/LIPIcs.SEA.2026.23
Exploiting Multi-Core Parallelism in Blockchain Validation and Construction

Authors: Arivarasan Karmegam, Lucianna Kiffer, and Antonio Fernández Anta

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Blockchain validators can reduce block processing time by exploiting multi-core CPUs, but deterministic execution must preserve a given total order while respecting transaction conflicts and per-block runtime limits. This paper systematically examines how validators can exploit multi-core parallelism during both block construction and execution without violating blockchain semantics. We formalize two validator-side optimization problems: (i) executing an already ordered block on p cores to minimize makespan while ensuring equivalence to sequential execution; and (ii) selecting and scheduling a subset of mempool transactions under a runtime limit B to maximize validator reward. For both, we develop exact Mixed-Integer Linear Programming (MILP) formulations that capture conflict, order, and capacity constraints, and propose fast deterministic heuristics that scale to realistic workloads. Using Ethereum mainnet traces and including a Solana-inspired declared-access baseline (Sol) for ordered-block scheduling and a simple reward-greedy baseline (RG) for block construction, we empirically quantify the trade-offs between optimality and runtime. MILPs quickly become intractable as heterogeneity or core count increases, whereas our heuristics run in milliseconds and achieve near-optimal quality. For ordered-block execution, heuristic makespans are typically within a few percent of the MILP solutions (and can even surpass the MILP incumbent when the solver times out), yielding up to 1.5 speedup with p = 2 and 2.3 speedup with p = 8 over sequential execution, despite tight ordering constraints. For block construction, the heuristic achieves 99-100% of the MILP optimum reward on homogeneous workloads, and 74-100% of an LP-relaxation upper bound on heterogeneous workloads, where exact optimization often times out. The resulting block-construction throughput scales close to linearly with p, reaching up to 7.9 speedup with p = 8 in our experiments. These results demonstrate that lightweight, conflict-aware scheduling and selection can unlock substantial parallelism in blockchain validation, bridging the gap between sequential execution and the true potential of multi-core hardware.
Cite as

Arivarasan Karmegam, Lucianna Kiffer, and Antonio Fernández Anta. Exploiting Multi-Core Parallelism in Blockchain Validation and Construction. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 23:1-23:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{karmegam_et_al:LIPIcs.SEA.2026.23,
  author =	{Karmegam, Arivarasan and Kiffer, Lucianna and Fern\'{a}ndez Anta, Antonio},
  title =	{{Exploiting Multi-Core Parallelism in Blockchain Validation and Construction}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{23:1--23:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.23},
  URN =		{urn:nbn:de:0030-drops-260271},
  doi =		{10.4230/LIPIcs.SEA.2026.23},
  annote =	{Keywords: Block construction, Block execution, Deterministic parallelism, Conflict-aware scheduling}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.31
Improved and Parameterized Algorithms for Online Multi-Level Aggregation

Authors: Young-San Lin and Alex Turoczy

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
We study the online multi-level aggregation problem with deadlines (MLAP-D) introduced by Bienkowski, Böhm, Byrka, Chrobak, Dürr, Folwarczný, Jeż, Sgall, Thang, and Veselý (ESA 2016, OR 2020). In this problem, requests arrive over time at the vertices of a given vertex-weighted tree, and each request has a deadline that it must be served by. The cost of serving a request equals the cost of a path from the root to the vertex where the request resides. Instead of serving each request individually, requests can be aggregated and served by transmitting a subtree from the root that spans the vertices on which the requests reside, to potentially be more cost-effective. The aggregated cost is the weight of the transmission subtree. The goal of MLAP-D is to find an aggregation solution that minimizes the total cost while serving all requests. MLAP-D generalizes some well-studied problems including the TCP acknowledgment problem and the joint replenishment problem, and arises in natural scenarios such as multi-casting, sensor networks, and supply chain management. We present improved and parameterized algorithms for MLAP-D. Our result is twofold. First, we present an e(D+1)-competitive algorithm where D is the depth of the tree. Second, we present an e(4H+2)-competitive algorithm where H is the caterpillar dimension of the tree. Here, H ≤ D and H ≤ log₂ |V| where |V| is the number of vertices in the given tree. The caterpillar dimension remains constant for rich but simple classes of trees, such as line graphs (H = 1), caterpillar graphs (H = 2), and lobster graphs (H = 3). To the best of our knowledge, this is the first online algorithm parameterized on a measure better than depth. The state-of-the-art online algorithms are 6(D+1)-competitive by Buchbinder, Feldman, Naor, and Talmon (SODA 2017) and O(log |V|)-competitive by Azar and Touitou (FOCS 2020). Our framework outperforms the state-of-the-art ratios when H = o(min{D,log₂ |V|}). Our memory-based algorithms extend transmission subtrees with a cost comparable to transmission subtrees used to serve previous requests. Our simple framework directly applies to trees with any structure and differs from the previous frameworks that reduce the problem to trees with specific structures.
Cite as

Young-San Lin and Alex Turoczy. Improved and Parameterized Algorithms for Online Multi-Level Aggregation. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lin_et_al:LIPIcs.SWAT.2026.31,
  author =	{Lin, Young-San and Turoczy, Alex},
  title =	{{Improved and Parameterized Algorithms for Online Multi-Level Aggregation}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{31:1--31:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.31},
  URN =		{urn:nbn:de:0030-drops-260673},
  doi =		{10.4230/LIPIcs.SWAT.2026.31},
  annote =	{Keywords: Online Algorithms, Approximation Algorithms, Graph Problems}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.35
Path-Reporting Distance Oracles for Vertex-Labeled Graphs

Authors: Ofer Neiman and Alon Spector

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
Let G = (V,E) be a weighted undirected graph, with n vertices. A distance oracle is a data structure that can quickly answer distance queries, with some stretch factor. A seminal work of [Thorup and Zwick, 2005], given an integer k ≥ 1, provides such an oracle with stretch 2k-1, query time O(k), and size O(k⋅ n^{1+1/k}). Furthermore, this oracle can also report a path in G corresponding to the returned distance. In this paper we focus on vertex-labeled graphs, in which each vertex is given a label from a set L of size 𝓁. A vertex-label distance oracle answers queries of the form (v,λ), where v ∈ V and λ ∈ L, by reporting (an approximation to) the distance from v to the closest vertex of label λ. Following [Danny Hermelin et al., 2011], it was shown in [Chechik, 2012] that for any integer k > 1, there exists a vertex-label distance oracle with stretch 4k-5, query time O(k), and size O(k⋅ n⋅ 𝓁^{1/k}). This state-of-the-art result suffers from two main drawbacks: The stretch is roughly a factor of 2 larger than in [Thorup and Zwick, 2005], and it is not path-reporting. We address these concerns in this work, and provide the following results. - First, we devise a path-reporting vertex-label distance oracle, at the cost of a slight increase in stretch and size. For any constant 0 < ε < 1, our oracle has stretch (4k-5)⋅(1+ε), query time O(k), and size O(n^{1+o(1)}⋅ 𝓁^{1/k}). - Second, we show how to improve the stretch to the optimal 2k-1, at the cost of mildly increasing the query time. Specifically, we devise a vertex-label distance oracle with stretch 2k-1, query time O(𝓁^{1/k}⋅log n), and size O(k⋅ n⋅ 𝓁^{1/k}).
Cite as

Ofer Neiman and Alon Spector. Path-Reporting Distance Oracles for Vertex-Labeled Graphs. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{neiman_et_al:LIPIcs.SWAT.2026.35,
  author =	{Neiman, Ofer and Spector, Alon},
  title =	{{Path-Reporting Distance Oracles for Vertex-Labeled Graphs}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.35},
  URN =		{urn:nbn:de:0030-drops-260719},
  doi =		{10.4230/LIPIcs.SWAT.2026.35},
  annote =	{Keywords: Graph Algorithms, Shortest Paths, Distance Oracles}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.8
Submodular Max-Min Allocation Under Identical Valuations

Authors: Kimon Boehmer

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
In the problem of Submodular Max-Min Allocation, we are given a set of items, a set of players, and monotone submodular valuation functions that represent the satisfaction of a player with a certain subset of items. The goal is to find an allocation of the items to the players that maximizes the lowest satisfaction among all players. We study this problem in the special case where all players have the same valuation function. We devise a greedy algorithm which gives a 0.4-approximation, improving the previously best factor of 10/27 ≈ 0.37 by Uziahu and Feige. Furthermore, we study the integrality gap of the configuration LP when players have identical valuations. By constructing a variable assignment to the dual from a primal integral solution, we give the first constant upper bound on the integrality gap for submodular valuations. Generalizing the result to the case where players' allocations must be independent in k given matroids, we derive a 𝒪(k)-estimation algorithm for max-min allocation subject to k matroid constraints under identical valuations.
Cite as

Kimon Boehmer. Submodular Max-Min Allocation Under Identical Valuations. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 8:1-8:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{boehmer:LIPIcs.SWAT.2026.8,
  author =	{Boehmer, Kimon},
  title =	{{Submodular Max-Min Allocation Under Identical Valuations}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{8:1--8:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.8},
  URN =		{urn:nbn:de:0030-drops-260446},
  doi =		{10.4230/LIPIcs.SWAT.2026.8},
  annote =	{Keywords: Submodularity, Approximation algorithms, Allocation, Configuration LP}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.15
One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming

Authors: Avinandan Das

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
This paper investigates the semi-streaming complexity of k-partial coloring, a generalization of proper graph coloring. For k ≥ 1, a k-partial coloring requires that each vertex v in an n-node graph is assigned a color such that at least min{k, deg(v)} of its neighbors are assigned colors different from its own. This framework naturally extends classical coloring problems: specifically, k-partial (k+1)-coloring and k-partial k-coloring generalize (Δ+1)-proper coloring and Δ-proper coloring, respectively. Prior works of Assadi, Chen, and Khanna [SODA 2019] and Assadi, Kumar, and Mittal [TheoretiCS 2023] show that both (Δ+1)-proper coloring and Δ-proper coloring admit one-pass randomized semi-streaming algorithms. We explore whether these efficiency gains extend to their partial coloring generalizations and reveal a sharp computational threshold: while k-partial (k+1)-coloring admits a one-pass randomized semi-streaming algorithm, the k-partial k-coloring remains semi-streaming intractable, effectively demonstrating a "dichotomy of one color" in the streaming model.
Cite as

Avinandan Das. One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{das:LIPIcs.SWAT.2026.15,
  author =	{Das, Avinandan},
  title =	{{One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.15},
  URN =		{urn:nbn:de:0030-drops-260515},
  doi =		{10.4230/LIPIcs.SWAT.2026.15},
  annote =	{Keywords: Graph Coloring, Semi-streaming algorithms, Lower bounds}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.22
Search-Space Reduction for Boolean MinCSPs via Essential Constraints

Authors: Bart M. P. Jansen and Ruben F. A. Verhaegh

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
For a fixed set ℱ of Boolean constraint types, a MinCSP(ℱ)-instance consists of a formula F that applies m constraints from ℱ to a set of n Boolean variables. The goal is to remove a minimum subset of constraint applications from F to make the remaining formula satisfiable. Previous work characterized how the choice of ℱ affects its polynomial-time solvability and approximability. We extend a recently introduced preprocessing framework for graph problems to the problem above. Rephrased in the context of CSPs, this framework defines a constraint application from a given formula F as c-essential if it is contained in all c-approximate solutions to F. Being able to efficiently detect these essential parts of a solution reduces the search space of any follow-up FPT algorithms parameterized by the solution size and yields an immediate asymptotic improvement to the runtime of such algorithms. In this work, we present a dichotomy theorem that distinguishes constraint sets ℱ for which c_ℱ-essential constraint applications can be detected efficiently for some c_{ℱ} ∈ 𝒪(1), from those for which this task is intractable under established complexity-theoretic conjectures. Our results show that for any set ℱ of bijunctive constraints, there is a polynomial-time algorithm that detects 𝒪(1)-essential constraint applications. This contrasts the fact that constant-factor approximating a bijunctive MinCSP(ℱ)-problem is intractable under the Unique Games Conjecture.
Cite as

Bart M. P. Jansen and Ruben F. A. Verhaegh. Search-Space Reduction for Boolean MinCSPs via Essential Constraints. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.SWAT.2026.22,
  author =	{Jansen, Bart M. P. and Verhaegh, Ruben F. A.},
  title =	{{Search-Space Reduction for Boolean MinCSPs via Essential Constraints}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.22},
  URN =		{urn:nbn:de:0030-drops-260586},
  doi =		{10.4230/LIPIcs.SWAT.2026.22},
  annote =	{Keywords: fixed-parameter tractability, constraint satisfaction problems}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2026.20
Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs

Authors: Jie Gao, Paweł Gawrychowski, Panos Giannopoulos, Wolfgang Mulzer, Satyam Singh, Frank Staals, and Meirav Zehavi

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract
A disk graph is the intersection graph of (closed) disks in the plane. We consider the classic problem of finding a maximum clique in a disk graph. For general disk graphs, the complexity of this problem is still open, but for unit disk graphs, it is well known to be in P. The currently fastest algorithm runs in time O(n^{7/3+ o(1)}), where n denotes the number of disks [Jared Espenant et al., 2023; J. Mark Keil and Debajyoti Mondal, 2025]. Moreover, for the case of disk graphs with t distinct radii, the problem has also recently been shown to be in XP. More specifically, it is solvable in time O^*(n^{2t}) [J. Mark Keil and Debajyoti Mondal, 2025]. In this paper, we present algorithms with improved running times by allowing for approximate solutions and by using randomization: [(i)] 1) for unit disk graphs, we give an algorithm that, with constant success probability, computes a (1-ε)-approximate maximum clique in expected time Õ(n/ε²); and 2) for disk graphs with t distinct radii, we give a parameterized approximation scheme that, with a constant success probability, computes a (1-ε)-approximate maximum clique in expected time Õ(f(t)⋅ (1/ε)^{O(t)} ⋅ n), for some (exponential) function f(t).
Cite as

Jie Gao, Paweł Gawrychowski, Panos Giannopoulos, Wolfgang Mulzer, Satyam Singh, Frank Staals, and Meirav Zehavi. Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.SWAT.2026.20,
  author =	{Gao, Jie and Gawrychowski, Pawe{\l} and Giannopoulos, Panos and Mulzer, Wolfgang and Singh, Satyam and Staals, Frank and Zehavi, Meirav},
  title =	{{Near-Linear and Parameterized Approximations for Maximum Cliques in Disk Graphs}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{20:1--20:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.20},
  URN =		{urn:nbn:de:0030-drops-260563},
  doi =		{10.4230/LIPIcs.SWAT.2026.20},
  annote =	{Keywords: Maximum Clique, Disk Graphs, Unit Disk Graphs, FPT Approximation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.13
Dynamic Light Spanners in Doubling Metrics

Authors: Sujoy Bhore, Jonathan Conroy, and Arnold Filtser

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
A t-spanner of a point set X in a metric space (𝒳, δ) is a graph G with vertex set P such that, for any pair of points u,v ∈ X, the distance between u and v in G is at most t times δ(u,v). We study the problem of maintaining a spanner for a dynamic point set X - that is, when X undergoes a sequence of insertions and deletions - in a metric space of constant doubling dimension. For any constant ε > 0, we maintain a (1+ε)-spanner of P whose total weight remains within a constant factor of the weight of the minimum spanning tree of X. Each update (insertion or deletion) can be performed in poly(log Φ) time, where Φ denotes the aspect ratio of X. Prior to our work, no efficient dynamic algorithm for maintaining a light-weight spanner was known even for point sets in low-dimensional Euclidean space.
Cite as

Sujoy Bhore, Jonathan Conroy, and Arnold Filtser. Dynamic Light Spanners in Doubling Metrics. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2026.13,
  author =	{Bhore, Sujoy and Conroy, Jonathan and Filtser, Arnold},
  title =	{{Dynamic Light Spanners in Doubling Metrics}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.13},
  URN =		{urn:nbn:de:0030-drops-258193},
  doi =		{10.4230/LIPIcs.SoCG.2026.13},
  annote =	{Keywords: Dynamic data structures, spanners, light-weight, Euclidean metrics, doubling metrics}
}
Document
Research
DOI: 10.4230/TGDK.4.1.4
Native Provenance Computation for Federated and Non-Federated SPARQL Queries

Authors: Zubaria Asma, Daniel Hernández, Luis Galárraga, Giorgos Flouris, Irini Fundulaki, and Katja Hose

Published in: TGDK, Volume 4, Issue 1 (2026). Transactions on Graph Data and Knowledge, Volume 4, Issue 1

Abstract
The popularity of knowledge graphs (KGs) owes credit to their flexible data model, which is suitable for data integration from multiple sources. Several KG-based applications, such as trust assessment, view maintenance, or data valuation on dynamic data, rely on the ability to compute provenance explanations for query results. This need becomes more urgent in federated query processing systems, which allow the online consumption of heterogeneous and decentralized Web data. However, the problem of computing and interacting with provenance has received little attention, especially in the federated setting. On those grounds, this paper introduces the NPCS (Native Provenance Computation for SPARQL) approach, and its federated variant Fed-NPCS, that compute provenance for SPARQL query results. Both approaches build upon spm-semirings to annotate the results of monotonic and non-monotonic SPARQL queries with their provenance. Due to their reliance on query rewriting techniques, the approaches are directly applicable to already deployed SPARQL engines and federations using different reification schemes, including RDF-star. Our experimental evaluation shows that our novel query rewriting approach brings significant run-time improvements w.r.t. the state-of-the-art across both centralized and federated settings. In centralized settings, our tests on two popular SPARQL engines (GraphDB and Stardog) reveal substantial runtime gains over existing query rewriting solutions, enabling scalability to RDF graphs with billions of triples. In federated settings, our experiments on the FedShop benchmark with GraphDB show the viability of Fed-NPCS for federations with up to 200 sources.
Cite as

Zubaria Asma, Daniel Hernández, Luis Galárraga, Giorgos Flouris, Irini Fundulaki, and Katja Hose. Native Provenance Computation for Federated and Non-Federated SPARQL Queries. In Transactions on Graph Data and Knowledge (TGDK), Volume 4, Issue 1, pp. 4:1-4:43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{asma_et_al:TGDK.4.1.4,
  author =	{Asma, Zubaria and Hern\'{a}ndez, Daniel and Gal\'{a}rraga, Luis and Flouris, Giorgos and Fundulaki, Irini and Hose, Katja},
  title =	{{Native Provenance Computation for Federated and Non-Federated SPARQL Queries}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{4:1--4:43},
  ISSN =	{2942-7517},
  year =	{2026},
  volume =	{4},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.4.1.4},
  URN =		{urn:nbn:de:0030-drops-259642},
  doi =		{10.4230/TGDK.4.1.4},
  annote =	{Keywords: native provenance computation, federated SPARQL queries, data provenance, NPCS, Fed-NPCS}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2026.12
The Complexity of Finding Missing Answer Repairs

Authors: Jesse Comer and Val Tannen

Published in: LIPIcs, Volume 365, 29th International Conference on Database Theory (ICDT 2026)

Abstract
We investigate the problem of identifying database repairs for missing tuples in query answers. We show that when the query is part of the input - the combined complexity setting - determining whether or not a repair exists is polynomial-time equivalent to the satisfiability problem for classes of queries admitting a weak form of projection and selection. We then identify the sub-classes of unions of conjunctive queries with negated atoms, defined by the relational algebra operations permitted to appear in the query, for which the minimal repair problem can be solved in polynomial time. In contrast, we show that the problem is NP-hard, as well as set cover-hard to approximate via strict reductions, whenever both projection and join are permitted in the input query. Additionally, we show that finding the size of a minimal repair for unions of conjunctive queries (with negated atoms permitted) is OptP[log(n)]-complete, while computing a minimal repair is possible with O(n²) queries to an NP oracle. With recursion permitted, the combined complexity of all of these variants increases significantly, with an EXP lower bound. However, from the data complexity perspective, we show that minimal repairs can be identified in polynomial time for all queries expressible as semi-positive datalog programs.
Cite as

Jesse Comer and Val Tannen. The Complexity of Finding Missing Answer Repairs. In 29th International Conference on Database Theory (ICDT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 365, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{comer_et_al:LIPIcs.ICDT.2026.12,
  author =	{Comer, Jesse and Tannen, Val},
  title =	{{The Complexity of Finding Missing Answer Repairs}},
  booktitle =	{29th International Conference on Database Theory (ICDT 2026)},
  pages =	{12:1--12:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-413-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{365},
  editor =	{ten Cate, Balder and Funk, Maurice},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2026.12},
  URN =		{urn:nbn:de:0030-drops-256265},
  doi =		{10.4230/LIPIcs.ICDT.2026.12},
  annote =	{Keywords: Missing answers, database repairs, datalog, computational complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.16
To Buy or Not to Buy: Online Rent-Or-Buy on Node-Weighted Graphs

Authors: Sander Borst and Moritz Venzin

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

Abstract
We study the rent-or-buy variant of the online Steiner forest problem on node- and edge-weighted graphs. For n-node graphs with at most ̄{n} nodes of non-zero weight, and at most k̃ different arriving terminal pairs, we obtain the following: - A deterministic, O(log n log ̄{n})-competitive algorithm against adaptive adversaries. This improves on the previous best, O(log⁴ n)-competitive algorithm obtained by the black-box reduction from [Yair Bartal et al., 2001] combined with the previously best deterministic algorithms for the simpler "buy-only" setting. - A deterministic, O(̄{n}log k̃)-competitive algorithm against adaptive adversaries. This generalizes the O(log k̃)-competitive algorithm for the purely edge-weighted setting from [Seeun Umboh, 2015]. - A randomized, O(log k̃ log ̄{n})-competitive algorithm against oblivious adversaries. All previous approaches were based on the randomized, black-box reduction from [Awerbuch et al., 2004] that achieves a O(log k̃ log n)-competitive ratio when combined with an algorithm for the "buy-only" setting. Our key technical ingredient is a novel charging scheme to an instance of online prize-collecting set cover. This allows us to extend the witness-technique of [Seeun Umboh, 2015] to the node-weighted setting and obtain refined guarantees with respect to ̄{n}, already in the much simpler "buy-only" setting.
Cite as

Sander Borst and Moritz Venzin. To Buy or Not to Buy: Online Rent-Or-Buy on Node-Weighted Graphs. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{borst_et_al:LIPIcs.STACS.2026.16,
  author =	{Borst, Sander and Venzin, Moritz},
  title =	{{To Buy or Not to Buy: Online Rent-Or-Buy on Node-Weighted Graphs}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{16:1--16:16},
  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.16},
  URN =		{urn:nbn:de:0030-drops-255054},
  doi =		{10.4230/LIPIcs.STACS.2026.16},
  annote =	{Keywords: online network design, node-weighted Steiner forest, derandomization}
}
  • Refine by Type
  • 116 Document/PDF
  • 92 Document/HTML

  • Refine by Publication Year
  • 27 2026
  • 69 2025
  • 5 2024
  • 1 2023
  • 2 2022
  • Show More...

  • Refine by Author
  • 18 Khanna, Sanjeev
  • 7 Assadi, Sepehr
  • 5 Putterman, Aaron
  • 4 Konrad, Christian
  • 4 Sudan, Madhu
  • Show More...

  • Refine by Series/Journal
  • 112 LIPIcs
  • 3 OASIcs
  • 1 TGDK

  • Refine by Classification
  • 22 Theory of computation → Streaming, sublinear and near linear time algorithms
  • 17 Theory of computation → Graph algorithms analysis
  • 13 Theory of computation → Approximation algorithms analysis
  • 6 Theory of computation → Communication complexity
  • 6 Theory of computation → Online algorithms
  • Show More...

  • Refine by Keyword
  • 5 Approximation Algorithms
  • 5 Graph Algorithms
  • 5 Sublinear Algorithms
  • 4 Sparsification
  • 4 communication complexity
  • 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