22 Search Results for "Královic, Richard"

Document
DOI: 10.4230/LIPIcs.FORC.2026.10
Packing Compact Subgraphs with Applications to Districting

Authors: Ho-Lin Chen, Po-Yu Chou, Prathamesh Dharangutte, Jie Gao, Shang-En Huang, and Fang-Yi Yu

Published in: LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026)

Abstract
Packing disjoint subgraphs in a given graph is a fundamental problem with many applications. Motivated by political districting, we focus on connected subgraphs that are compact (e.g., having constant radius from a single center vertex) and that satisfy additional composition requirements, such as a minimum population/weight threshold or balanced weight types (e.g., political affiliations). We aim to maximize coverage by disjoint districts that meet these requirements. In this work, we present new results that substantially improve the previously known bounds on balanced star districts for planar and minor-free graphs [Prathamesh Dharangutte et al., 2025]. In particular, we improve the approximation factor from O(log n) to O(1) for packing balanced star districts using the exact same algorithm, but with a refined analysis. We also extend the results beyond planar graphs to minor-free graphs and an even broader family of graphs of bounded expansion. Additionally, we obtain an O(1) approximation for packing radius-k districts (with a constant k) in planar and apex-minor-free graphs. In order to get a (1+ε) approximation on the max coverage, we show that this can be achieved if we allow a slight relaxation of the balancedness parameters (by a factor that can be made arbitrarily close to 1), for bounded radius-k districts on planar and apex-minor-free graphs. We show that all of these results can also be obtained if we enforce a minimum weight threshold for each district as the composition requirement, rather than balancedness. We present various results on hardness and hardness of approximation for this variant, by graph and district types.
Cite as

Ho-Lin Chen, Po-Yu Chou, Prathamesh Dharangutte, Jie Gao, Shang-En Huang, and Fang-Yi Yu. Packing Compact Subgraphs with Applications to Districting. In 7th Symposium on Foundations of Responsible Computing (FORC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 368, pp. 10:1-10:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.FORC.2026.10,
  author =	{Chen, Ho-Lin and Chou, Po-Yu and Dharangutte, Prathamesh and Gao, Jie and Huang, Shang-En and Yu, Fang-Yi},
  title =	{{Packing Compact Subgraphs with Applications to Districting}},
  booktitle =	{7th Symposium on Foundations of Responsible Computing (FORC 2026)},
  pages =	{10:1--10:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-419-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{368},
  editor =	{Lin, Huijia (Rachel)},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.10},
  URN =		{urn:nbn:de:0030-drops-259820},
  doi =		{10.4230/LIPIcs.FORC.2026.10},
  annote =	{Keywords: Approximation algorithms, algorithmic fairness}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.25
Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing

Authors: Marek Černý and Tim Seppelt

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

Abstract
Two graphs G and H are homomorphism indistinguishable over a graph class ℱ if they admit the same number of homomorphisms from every graph F ∈ ℱ. Many graph isomorphism relaxations such as (quantum) isomorphism and cospectrality can be characterised as homomorphism indistinguishability over specific graph classes. Thereby, the problems HomInd(ℱ) of deciding homomorphism indistinguishability over ℱ subsume diverse graph isomorphism relaxations whose complexities range from logspace to undecidable. Establishing the first general result on the complexity of HomInd(ℱ), Seppelt (MFCS 2024) showed that HomInd(ℱ) is in randomised polynomial time for every graph class ℱ of bounded treewidth that can be defined in counting monadic second-order logic CMSO₂. We show that this algorithm is conditionally optimal, i.e. it cannot be derandomised unless polynomial identity testing is in P. For CMSO₂-definable graph classes ℱ of bounded pathwidth, we improve the previous complexity upper bound for HomInd(ℱ) from P to C_ = L and show that this is tight. Secondarily, we establish a connection between homomorphism indistinguishability and multiplicity automata equivalence which allows us to pinpoint the complexity of the latter problem as C_ = L-complete.
Cite as

Marek Černý and Tim Seppelt. Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 25:1-25:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cerny_et_al:LIPIcs.STACS.2026.25,
  author =	{\v{C}ern\'{y}, Marek and Seppelt, Tim},
  title =	{{Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{25:1--25:20},
  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.25},
  URN =		{urn:nbn:de:0030-drops-255144},
  doi =		{10.4230/LIPIcs.STACS.2026.25},
  annote =	{Keywords: treewidth, Courcelle’s theorem, logspace, multiplicity automata, polynomial identity testing}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.44
Optimal Average Disk-Inspection via Fermat’s Principle

Authors: Konstantinos Georgiou

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

Abstract
This work resolves the optimal average-case cost of the Disk-Inspection problem, a variant of Bellman’s 1955 lost-in-a-forest problem. In Disk-Inspection, a mobile agent starts at the center of a unit disk and follows a trajectory that inspects perimeter points whenever the disk does not obstruct visibility. The worst-case cost was solved optimally in 1957 by Isbell [Isbell, 1957], but the average-case version remained open, with heuristic upper bounds proposed by Gluss [Gluss, 1961] in 1961 and improved only recently in [Conley and Georgiou, 2025]. Our approach applies Fermat’s Principle of Least Time from optics to the discretization framework of [Conley and Georgiou, 2025], showing that optimal solutions are captured by a one-parameter family of recurrences independent of the discretization size. In the continuum limit these recurrences give rise to a single-parameter optimal control problem, whose trajectories coincide with limiting solutions of the original Disk-Inspection problem. A crucial step is proving that the optimal initial condition generates a trajectory that avoids the unit disk, thereby validating the optics formulation and reducing the many-variable optimization to a rigorous one-parameter problem. In particular, this disproves Gluss’s conjecture [Gluss, 1961] that optimal trajectories must touch the disk. Our analysis determines the exact optimal average-case inspection cost, equal to 3.549259… and certified to at least six digits of accuracy.
Cite as

Konstantinos Georgiou. Optimal Average Disk-Inspection via Fermat’s Principle. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{georgiou:LIPIcs.STACS.2026.44,
  author =	{Georgiou, Konstantinos},
  title =	{{Optimal Average Disk-Inspection via Fermat’s Principle}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{44:1--44:19},
  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.44},
  URN =		{urn:nbn:de:0030-drops-255331},
  doi =		{10.4230/LIPIcs.STACS.2026.44},
  annote =	{Keywords: Inspection, Disk, Average-Case Performance}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.43
Stealing from the Dragon’s Hoard: Online Unbounded Knapsack With Removal

Authors: Matthias Gehnen and Moritz Stocker

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

Abstract
We introduce the Online Unbounded Knapsack Problem with Removal, a variation of the well-known Online Knapsack Problem. Items, each with a weight and value, arrive online and an algorithm must decide on whether or not to pack them into a knapsack with a fixed weight limit. An item may be packed an arbitrary number of times and items may be removed from the knapsack at any time without cost. The goal is to maximize the total value of items packed, while respecting a weight limit. We show that this is one of the very few natural online knapsack variants that allow for competitive deterministic algorithms in the general setting, by providing an algorithm with competitivity 1.6911. We complement this with a lower bound of 1.5877. We also analyze the proportional setting, where the weight and value of any single item agree, and show that deterministic algorithms can be exactly 3/2-competitive. Lastly, we give lower and upper bounds of 6/5 and 4/3 on the competitivity of randomized algorithms in this setting.
Cite as

Matthias Gehnen and Moritz Stocker. Stealing from the Dragon’s Hoard: Online Unbounded Knapsack With Removal. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gehnen_et_al:LIPIcs.STACS.2026.43,
  author =	{Gehnen, Matthias and Stocker, Moritz},
  title =	{{Stealing from the Dragon’s Hoard: Online Unbounded Knapsack With Removal}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{43:1--43: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.43},
  URN =		{urn:nbn:de:0030-drops-255327},
  doi =		{10.4230/LIPIcs.STACS.2026.43},
  annote =	{Keywords: online problems, online knapsack, unbounded knapsack, removal}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.45
Fairness in the k-Server Problem

Authors: Mohammadreza Daneshvaramoli, Mohammad Hajiesmaili, Shahin Kamali, Helia Karisani, and Cameron Musco

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

Abstract
We initiate a formal study of fairness for the k-server problem, where the objective is not only to minimize the total movement cost, but also to distribute the cost equitably among servers. We first define a general notion of (α,β)-fairness, where, for parameters α ≥ 1 and β ≥ 0, no server incurs more than an α/k-fraction of the total cost plus an additive term β. We then show that fairness can be achieved without a loss in competitiveness in both the offline and online settings. In the offline setting, we give a deterministic algorithm that, for any ε > 0, transforms any optimal solution into an (α,β)-fair solution for α = 1 + ε and β = O(diam ⋅ log k / ε), while increasing the cost of the solution by just an additive O(diam ⋅ k log k / ε) term. Here diam is the diameter of the underlying metric space. We give a similar result in the online setting, showing that any competitive algorithm can be transformed into a randomized online algorithm that is fair with high probability against an oblivious adversary and still competitive up to a small loss. The above results leave open a significant question: can fairness be achieved in the online setting, either with a deterministic algorithm or a randomized algorithm, against a fully adaptive adversary? We make progress towards answering this question, showing that the classic deterministic Double Coverage Algorithm (DCA) is fair on line metrics and on tree metrics when k = 2. However, we also show a negative result: DCA fails to be fair for any non-vacuous parameters on general tree metrics. We further show that on uniform metrics (i.e., the paging problem), the deterministic First-In First-Out (FIFO) algorithm is fair. We show that any "marking algorithm", including the Least Recently Used (LRU) algorithm, also satisfies a weaker, but still meaningful notion of fairness.
Cite as

Mohammadreza Daneshvaramoli, Mohammad Hajiesmaili, Shahin Kamali, Helia Karisani, and Cameron Musco. Fairness in the k-Server Problem. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 45:1-45:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{daneshvaramoli_et_al:LIPIcs.ITCS.2026.45,
  author =	{Daneshvaramoli, Mohammadreza and Hajiesmaili, Mohammad and Kamali, Shahin and Karisani, Helia and Musco, Cameron},
  title =	{{Fairness in the k-Server Problem}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{45:1--45:21},
  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.45},
  URN =		{urn:nbn:de:0030-drops-253328},
  doi =		{10.4230/LIPIcs.ITCS.2026.45},
  annote =	{Keywords: k-server problem, online algorithms, fairness, competitive analysis}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.32
Time-Optimal k-Server

Authors: Fabian Frei, Dennis Komm, Moritz Stocker, and Philip Whittington

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

Abstract
The time-optimal k-server problem minimizes the time spent instead of the distance traveled when serving n requests, appearing one after the other, with k servers in a metric space. The classical distance model was motivated by a hard disk with k heads. Instead of minimal head movements, the time model aims for optimal reading speeds. This paper provides a lower bound of 2k-1 on the competitive ratio of any deterministic online algorithm for the time-optimal k-server problem on a specifically designed metric space. This lower bound coincides with the best known upper bound on the competitive ratio for the classical k-server problem, achieved by the famous work function algorithm. We provide further lower bounds of k+1 for all Euclidean spaces and k for uniform metric spaces. Our most technical result, proven by applying Yao’s principle to a suitable instance distribution, is a lower bound of k+H_k-1 that holds even for randomized algorithms, which contrasts with the best known lower bound for the classical problem, which is polylogarithmic in k. We hope to initiate further intensive study of this natural problem.
Cite as

Fabian Frei, Dennis Komm, Moritz Stocker, and Philip Whittington. Time-Optimal k-Server. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{frei_et_al:LIPIcs.ISAAC.2025.32,
  author =	{Frei, Fabian and Komm, Dennis and Stocker, Moritz and Whittington, Philip},
  title =	{{Time-Optimal k-Server}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{32:1--32:17},
  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.32},
  URN =		{urn:nbn:de:0030-drops-249407},
  doi =		{10.4230/LIPIcs.ISAAC.2025.32},
  annote =	{Keywords: k-server problem, optimizing time instead of distance, deterministic and randomized algorithms, Yao’s principle}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.30
Team Formation and Applications

Authors: Yuval Emek, Shay Kutten, Ido Rafael, and Gadi Taubenfeld

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
A novel long-lived distributed problem, called Team Formation (TF), is introduced together with a message- and time-efficient randomized algorithm. The problem is defined over the asynchronous model with a complete communication graph, using bounded size messages, where a certain fraction of the nodes may experience a generalized, strictly stronger, version of initial failures. The goal of a TF algorithm is to assemble tokens injected by the environment, in a distributed manner, into teams of size σ, where σ is a parameter of the problem. The usefulness of TF is demonstrated by using it to derive efficient algorithms for many distributed problems. Specifically, we show that various (one-shot as well as long-lived) distributed problems reduce to TF. This includes well-known (and extensively studied) distributed problems such as several versions of leader election and threshold detection. For example, we are the first to break the linear message complexity bound for asynchronous implicit leader election. We also improve the time complexity of message-optimal algorithms for asynchronous explicit leader election. Other distributed problems that reduce to TF are new ones, including matching players in online gaming platforms, a generalization of gathering, constructing a perfect matching in an induced subgraph of the complete graph, and more. To complement our positive contribution, we establish a tight lower bound on the message complexity of TF algorithms.
Cite as

Yuval Emek, Shay Kutten, Ido Rafael, and Gadi Taubenfeld. Team Formation and Applications. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 30:1-30:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.DISC.2025.30,
  author =	{Emek, Yuval and Kutten, Shay and Rafael, Ido and Taubenfeld, Gadi},
  title =	{{Team Formation and Applications}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{30:1--30:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.30},
  URN =		{urn:nbn:de:0030-drops-248474},
  doi =		{10.4230/LIPIcs.DISC.2025.30},
  annote =	{Keywords: asynchronous message-passing, complete communication graph, initial failures, leader election, matching}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.12
Distributed Computation with Local Advice

Authors: Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, and Jukka Suomela

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Algorithms with advice have received ample attention in the distributed and online settings, and they have recently proven useful also in dynamic settings. In this work we study local computation with advice: the goal is to solve a graph problem Π with a distributed algorithm in T(Δ) communication rounds, for some function T that only depends on the maximum degree Δ of the graph, and the key question is how many bits of advice per node are needed. Some of our results regard Locally Checkable Labeling problems (LCLs), which is an important family of problems that includes various coloring and orientation problems on finite-degree graphs. These are constraint-satisfaction graph problems that can be defined with a finite set of valid input/output-labeled neighborhoods. Our main results are: 1) Any locally checkable labeling problem can be solved with only 1 bit of advice per node in graphs with sub-exponential growth (the number of nodes within radius r is sub-exponential in r; for example, grids are such graphs). Moreover, we can make the set of nodes that carry advice bits arbitrarily sparse. As a corollary, any locally checkable labeling problem admits a locally checkable proof with 1 bit per node in graphs with sub-exponential growth. 2) The assumption of sub-exponential growth is complemented by a conditional lower bound: assuming the Exponential-Time Hypothesis, there are locally checkable labeling problems that cannot be solved in general with any constant number of bits per node. 3) In any graph we can find an almost-balanced orientation (indegrees and outdegrees differ by at most one) with 1 bit of advice per node, and again we can make the advice arbitrarily sparse. As a corollary, we can also compress an arbitrary subset of edges so that a node of degree d stores only d/2 + 2 bits, and we can decompress it locally, in T(Δ) rounds. 4) In any graph of maximum degree Δ, we can find a Δ-coloring (if it exists) with 1 bit of advice per node, and again, we can make the advice arbitrarily sparse. 5) In any 3-colorable graph, we can find a 3-coloring with 1 bit of advice per node. As a corollary, in bounded-degree graphs there is a locally checkable proof that certifies 3-colorability with 1 bit of advice per node, while prior work shows that this is not possible with a proof labeling scheme (PLS), which is a more restricted setting where the verifier can only see up to distance 1. Our work shows that for many problems the key threshold is not whether we can achieve 1 bit of advice per node, but whether we can make the advice arbitrarily sparse. To formalize this idea, we develop a general framework of composable schemas that enables us to build algorithms for local computation with advice in a modular fashion: once we have (1) a schema for solving Π₁ and (2) a schema for solving Π₂ assuming an oracle for Π₁, we can also compose them and obtain (3) a schema that solves Π₂ without the oracle. It turns out that many natural problems admit composable schemas, all of them can be solved with only 1 bit of advice, and we can make the advice arbitrarily sparse.
Cite as

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, and Jukka Suomela. Distributed Computation with Local Advice. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.DISC.2025.12,
  author =	{Balliu, Alkida and Brandt, Sebastian and Kuhn, Fabian and Nowicki, Krzysztof and Olivetti, Dennis and Rotenberg, Eva and Suomela, Jukka},
  title =	{{Distributed Computation with Local Advice}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{12:1--12:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.12},
  URN =		{urn:nbn:de:0030-drops-248295},
  doi =		{10.4230/LIPIcs.DISC.2025.12},
  annote =	{Keywords: Distributed graph algorithms, LOCAL model, computation with advice, locally checkable labeling problems, proof labeling schemes, locally checkable proofs, graph coloring, exponential-time hypothesis}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.16
Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole

Authors: Adri Bhattacharya, Pritam Goswami, Evangelos Bampas, and Partha Sarathi Mandal

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
In this paper, we investigate the following question: "How can a group of initially co-located mobile agents perpetually explore an unknown graph, when one stationary node occasionally behaves maliciously, under the control of an adversary?" This malicious node is termed as "Byzantine black hole (BBH)" and at any given round it may choose to destroy all visiting agents, or none of them. While investigating this question, we found out that this subtle power turns out to drastically undermine even basic exploration strategies which have been proposed in the context of a classical, always active, black hole. We study this perpetual exploration problem in the presence of at most one BBH, without initial knowledge of the network size. Since the underlying graph may be 1-connected, perpetual exploration of the entire graph may be infeasible. Accordingly, we define two variants of the problem, termed as PerpExploration-BBH and PerpExploration-BBH-Home. In the former, the agents are tasked to perform perpetual exploration of at least one component, obtained after the exclusion of the BBH. In the latter, the agents are tasked to perform perpetual exploration of the component which contains the home node, where agents are initially co-located. Naturally, PerpExploration-BBH-Home is a special case of PerpExploration-BBH. The mobile agents are controlled by a synchronous scheduler, and they communicate via face-to-face model of communication. The main objective in this paper is to determine the minimum number of agents necessary and sufficient to solve these problems. We first consider the problems in acyclic networks, and we obtain optimal algorithms that solve PerpExploration-BBH with 4 agents, and PerpExploration-BBH-Home with 6 agents in trees. The lower bounds hold even in path graphs. In general graphs, we give a non-trivial lower bound of 2Δ-1 agents for PerpExploration-BBH, and an upper bound of 3Δ+3 agents for PerpExploration-BBH-Home. To the best of our knowledge, this is the first paper that studies a variant of a black hole in arbitrary networks, without initial topological knowledge about the network.
Cite as

Adri Bhattacharya, Pritam Goswami, Evangelos Bampas, and Partha Sarathi Mandal. Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.DISC.2025.16,
  author =	{Bhattacharya, Adri and Goswami, Pritam and Bampas, Evangelos and Mandal, Partha Sarathi},
  title =	{{Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.16},
  URN =		{urn:nbn:de:0030-drops-248333},
  doi =		{10.4230/LIPIcs.DISC.2025.16},
  annote =	{Keywords: mobile agents, perpetual exploration, malicious host, Byzantine black hole}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.14
Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms

Authors: Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista, Michael T. Goodrich, and Martin Nöllenburg

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

Abstract
We introduce a quantum dynamic programming framework that allows us to directly extend to the quantum realm a large body of classical dynamic programming algorithms. The corresponding quantum dynamic programming algorithms retain the same space complexity as their classical counterpart, while achieving a computational speedup. For a combinatorial (search or optimization) problem P and an instance I of P, such a speedup can be expressed in terms of the average degree δ of the {dependency digraph} G_𝒫(I) of I, determined by a recursive formulation of P. The nodes of this graph are the subproblems of P induced by I and its arcs are directed from each subproblem to those on whose solution it relies. In particular, our framework allows us to solve the considered problems in Õ(|V(G_𝒫(I))| √δ) time. As an example, we obtain a quantum version of the Bellman-Ford algorithm for computing shortest paths from a single source vertex to all the other vertices in a weighted n-vertex digraph with m edges that runs in Õ(n√{nm}) time, which improves the best known classical upper bound when m ∈ Ω(n^{1.4}).
Cite as

Susanna Caroppo, Giordano Da Lozzo, Giuseppe Di Battista, Michael T. Goodrich, and Martin Nöllenburg. Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 14:1-14:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{caroppo_et_al:LIPIcs.WADS.2025.14,
  author =	{Caroppo, Susanna and Da Lozzo, Giordano and Di Battista, Giuseppe and Goodrich, Michael T. and N\"{o}llenburg, Martin},
  title =	{{Quantum Speedups for Polynomial-Time Dynamic Programming Algorithms}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{14:1--14:22},
  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.14},
  URN =		{urn:nbn:de:0030-drops-242454},
  doi =		{10.4230/LIPIcs.WADS.2025.14},
  annote =	{Keywords: Dynamic Programming, Quantum Algorithms, Quantum Random Access Memory}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.12
Online Knapsack Problems with Estimates

Authors: Jakub Balabán, Matthias Gehnen, Henri Lotze, Finn Seesemann, and Moritz Stocker

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

Abstract
Imagine you are a computer scientist who enjoys attending conferences or workshops within the year. Sadly, your travel budget is limited, so you must select a subset of events you can travel to. When you are aware of all possible events and their costs at the beginning of the year, you can select the subset of the possible events that maximizes your happiness and is within your budget. On the other hand, if you are blind about the options, you will likely have a hard time when trying to decide if you want to register somewhere or not, and will likely regret decisions you made in the future. These scenarios can be modeled by knapsack variants, either by an offline or an online problem. However, both scenarios are somewhat unrealistic: Usually, you will not know the exact costs of each workshop at the beginning of the year. The online version, however, is too pessimistic, as you might already know which options there are and how much they cost roughly. At some point, you have to decide whether to register for some workshop, but then you are aware of the conference fee and the flight and hotel prices. We model this problem within the setting of online knapsack problems with estimates: in the beginning, you receive a list of potential items with their estimated size as well as the accuracy of the estimates. Then, the items are revealed one by one in an online fashion with their actual size, and you need to decide whether to take one or not. In this article, we show a best-possible algorithm for each estimate accuracy δ (i.e., when each actual item size can deviate by ± δ from the announced size) for both the simple knapsack (also known as subset sum problem) and the simple knapsack with removability.
Cite as

Jakub Balabán, Matthias Gehnen, Henri Lotze, Finn Seesemann, and Moritz Stocker. Online Knapsack Problems with Estimates. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{balaban_et_al:LIPIcs.MFCS.2025.12,
  author =	{Balab\'{a}n, Jakub and Gehnen, Matthias and Lotze, Henri and Seesemann, Finn and Stocker, Moritz},
  title =	{{Online Knapsack Problems with Estimates}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{12:1--12:19},
  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.12},
  URN =		{urn:nbn:de:0030-drops-241190},
  doi =		{10.4230/LIPIcs.MFCS.2025.12},
  annote =	{Keywords: Knapsack, Online Knapsack, Removability, Estimate, Prediction}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.20
Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components

Authors: Sriram Bhyravarapu, Pritesh Kumar, Madhumita Kundu, Shivesh K. Roy, Sahiba, and Saket Saurabh

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

Abstract
Motivated by the growing interest in graph clustering and the framework proposed during the Dagstuhl Seminar 23331, we consider a natural specialization of this general approach (as also suggested during the seminar). The seminar introduced a broad perspective on clustering, where the goal is to partition a graph into connected components (or "clusters") that satisfy simple structural integrity constraints - not necessarily limited to cliques. In our work, we focus on the case where each cluster is required to have bounded vertex cover number. Specifically, a connected component C satisfies this condition if there exists a set S ⊆ V(C) with |S| ≤ d such that C - S is an independent set. We study this within the framework of the {Vertex Deletion to d-Vertex Cover Components} ({Vertex Deletion to d-VCC}) problem: given a graph G and an integer k, the task is to determine whether there exists a vertex set S ⊆ V(G) of size at most k such that every connected component of G - S has vertex cover number at most d. We also examine the edge-deletion variant, {Edge Deletion to d-Vertex Cover Components} ({Edge Deletion to d-VCC}), where the goal is to delete at most k edges so that each connected component of the resulting graph has vertex cover number at most d. We obtain following results. 1) {Vertex Deletion to d-VCC} admits a kernel with {𝒪}(d⁶k³) vertices and {𝒪}(d⁹k⁴) edges. 2) {Edge Deletion to d-VCC}, admits a kernel with {𝒪}(d⁴k) vertices and {𝒪}(d⁵k) edges. Both of our kernelization algorithms run in time 𝒪(1.253^d ⋅ (kd)^{𝒪(1)} ⋅ n log n). It is important to note that, unless the Exponential Time Hypothesis (ETH) fails, the dependence on d cannot be improved to 2^{o(d)}, as the case k = 0 reduces to solving the classical Vertex Cover problem, which is known to require 2^{Ω(d)} time under ETH. A key ingredient in our kernelization algorithms is a structural result about the hereditary graph class 𝒢_d, consisting of graphs in which every connected component has vertex cover number at most d. We show that 𝒢_d admits a finite obstruction set (with respect to the induced subgraph relation) of size 2^{𝒪(d²)}, where each obstruction graph has at most 3d + 2 vertices. This combinatorial result may be of independent interest.
Cite as

Sriram Bhyravarapu, Pritesh Kumar, Madhumita Kundu, Shivesh K. Roy, Sahiba, and Saket Saurabh. Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bhyravarapu_et_al:LIPIcs.MFCS.2025.20,
  author =	{Bhyravarapu, Sriram and Kumar, Pritesh and Kundu, Madhumita and Roy, Shivesh K. and Sahiba and Saurabh, Saket},
  title =	{{Kernelization in Almost Linear Time for Clustering into Bounded Vertex Cover Components}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{20:1--20: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.20},
  URN =		{urn:nbn:de:0030-drops-241276},
  doi =		{10.4230/LIPIcs.MFCS.2025.20},
  annote =	{Keywords: Parameterized complexity, Polynomial Kernels, Vertex Cover, Finite Forbidden Characterization}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.158
Restricted CSPs and F-Free Digraph Algorithmics

Authors: Santiago Guzmán-Pro and Barnaby Martin

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

Abstract
In recent years, much attention has been placed on the complexity of graph homomorphism problems when the input is restricted to ℙ_k-free and ℙ_k-subgraph-free graphs. We consider the directed version of this research line, by addressing the question is it true that digraph homomorphism problems CSP(H) have a P versus NP-complete dichotomy when the input is restricted to ℙ→_k-free (resp. ℙ→_k-subgraph-free) digraphs? Our main contribution in this direction shows that if CSP(H) is NP-complete, then there is a positive integer N such that CSP(H) remains NP-hard even for ℙ→_N-subgraph-free digraphs. Moreover, CSP(H) becomes polynomial-time solvable for ℙ→_{N-1}-subgraph-free acyclic digraphs. We then verify the questions above for digraphs on three vertices and a family of smooth tournaments. We prove these results by establishing a connection between F-(subgraph)-free algorithmics and constraint satisfaction theory. On the way, we introduce restricted CSPs, i.e., problems of the form CSP(H) restricted to yes-instances of CSP(H') - these were called restricted homomorphism problems by Hell and Nešetřil. Another main result of this paper presents a P versus NP-complete dichotomy for these problems. Moreover, this complexity dichotomy is accompanied by an algebraic dichotomy in the spirit of the finite domain CSP dichotomy.
Cite as

Santiago Guzmán-Pro and Barnaby Martin. Restricted CSPs and F-Free Digraph Algorithmics. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 158:1-158:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{guzmanpro_et_al:LIPIcs.ICALP.2025.158,
  author =	{Guzm\'{a}n-Pro, Santiago and Martin, Barnaby},
  title =	{{Restricted CSPs and F-Free Digraph Algorithmics}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{158:1--158:21},
  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.158},
  URN =		{urn:nbn:de:0030-drops-235352},
  doi =		{10.4230/LIPIcs.ICALP.2025.158},
  annote =	{Keywords: Digraph homomorphisms, constraint satisfaction problems, subgraph-free algorithmics}
}
Document
DOI: 10.4230/LIPIcs.CPM.2025.28
Faster Approximate Elastic-Degenerate String Matching - Part A

Authors: Solon P. Pissis, Jakub Radoszewski, and Wiktor Zuba

Published in: LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)

Abstract
An elastic-degenerate (ED) string 𝐓 is a sequence 𝐓 = 𝐓[1] ⋯ 𝐓[n] of n finite sets of strings. The cardinality m of 𝐓 is the total number of strings in 𝐓[i], for all i ∈ [1..n]. The size N of 𝐓 is the total length of all m strings of 𝐓. ED strings have been introduced to represent a set of closely-related DNA sequences. Let P = P[1..p] be a pattern of length p and k > 0 be an integer. We consider the problem of k-Approximate ED String Matching (EDSM): searching k-approximate occurrences of P in the language of 𝐓. We call k-Approximate EDSM under the Hamming distance, k-Mismatch EDSM; and we call k-Approximate EDSM under edit distance, k-Edit EDSM. Bernardini et al. (Theoretical Computer Science, 2020) showed a simple 𝒪(k m p + kN)-time algorithm for k-Mismatch EDSM and an 𝒪(k² m p + kN)-time algorithm for k-Edit EDSM. We improve the dependency on k in both results, obtaining an Õ(k^{2/3}mp+√kN)-time algorithm for k-Mismatch EDSM and an Õ(kmp+ kN)-time algorithm for k-Edit EDSM. Bernardini et al. (Theory of Computing Systems, 2024) presented several algorithms for 1-Approximate EDSM working in Õ(np²+N) time. They have also left the possibility to generalize these solutions for k > 1 as an open problem. We improve the runtime of their solution for 1-Mismatch and 1-Edit EDSM from Õ(np²+N) to 𝒪(np²+N). We further show algorithms for k-Approximate EDSM for the Hamming and edit distances working in Õ(np² + N) time, for any constant k > 0. Finally, we show how our techniques can be applied to improve upon the complexity of the k-Approximate ED String Intersection and k-Approximate Doubly EDSM problems that were introduced very recently by Gabory et al. (Information and Computation, 2025).
Cite as

Solon P. Pissis, Jakub Radoszewski, and Wiktor Zuba. Faster Approximate Elastic-Degenerate String Matching - Part A. In 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 331, pp. 28:1-28:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pissis_et_al:LIPIcs.CPM.2025.28,
  author =	{Pissis, Solon P. and Radoszewski, Jakub and Zuba, Wiktor},
  title =	{{Faster Approximate Elastic-Degenerate String Matching - Part A}},
  booktitle =	{36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)},
  pages =	{28:1--28:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-369-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{331},
  editor =	{Bonizzoni, Paola and M\"{a}kinen, Veli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.28},
  URN =		{urn:nbn:de:0030-drops-231227},
  doi =		{10.4230/LIPIcs.CPM.2025.28},
  annote =	{Keywords: ED string, approximate string matching, Hamming distance, edit distance}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.8
Matching and Edge Cover in Temporal Graphs

Authors: Lapo Cioni, Riccardo Dondi, Andrea Marino, Jason Schoeters, and Ana Silva

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
Temporal graphs are a special class of graphs for which a temporal component is added to edges, that is, each edge possesses a set of times at which it is available and can be traversed. Many classical problems on graphs can be translated to temporal graphs, and the results may differ. In this paper, we define the {Temporal Edge Cover} and {Temporal Matching} problems and show that they are NP-complete even when fixing the lifetime or when the underlying graph is a tree. We then describe two FPT algorithms, with parameters lifetime and treewidth, that solve the two problems. We also find lower bounds for the approximation of the two problems and give two approximation algorithms which match these bounds. Finally, we discuss the differences between the problems in the temporal and the static framework.
Cite as

Lapo Cioni, Riccardo Dondi, Andrea Marino, Jason Schoeters, and Ana Silva. Matching and Edge Cover in Temporal Graphs. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cioni_et_al:LIPIcs.SAND.2025.8,
  author =	{Cioni, Lapo and Dondi, Riccardo and Marino, Andrea and Schoeters, Jason and Silva, Ana},
  title =	{{Matching and Edge Cover in Temporal Graphs}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.8},
  URN =		{urn:nbn:de:0030-drops-230614},
  doi =		{10.4230/LIPIcs.SAND.2025.8},
  annote =	{Keywords: graphs, temporal graphs, edge cover, matching, parameterized algorithm, approximation algorithm}
}
  • Refine by Type
  • 22 Document/PDF
  • 16 Document/HTML

  • Refine by Publication Year
  • 5 2026
  • 11 2025
  • 2 2020
  • 1 2019
  • 1 2016
  • Show More...

  • Refine by Author
  • 4 Komm, Dennis
  • 3 Stocker, Moritz
  • 2 Bhattacharya, Adri
  • 2 Frei, Fabian
  • 2 Gehnen, Matthias
  • Show More...

  • Refine by Series/Journal
  • 20 LIPIcs
  • 1 OASIcs
  • 1 LITES

  • Refine by Classification
  • 4 Theory of computation → Distributed algorithms
  • 3 Mathematics of computing → Graph algorithms
  • 3 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Design and analysis of algorithms
  • 2 Theory of computation → Online algorithms
  • Show More...

  • Refine by Keyword
  • 2 Randomization
  • 2 Vertex Cover
  • 2 k-server problem
  • 2 matching
  • 2 online 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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact