6 Search Results for "Prałat, Paweł"

Document
DOI: 10.4230/LIPIcs.DISC.2025.40
On the Randomized Locality of Matching Problems in Regular Graphs

Authors: Seri Khoury, Manish Purohit, Aaron Schild, and Joshua R. Wang

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

Abstract
The main goal in distributed symmetry-breaking is to understand the locality of problems: the radius of the neighborhood that a node must explore to determine its part of a global solution. In this work, we study the locality of matching problems in the family of regular graphs, which is one of the main benchmarks for establishing lower bounds on the locality of symmetry-breaking problems, as well as for obtaining classification results. Our main results are summarized as follows: 1) Approximate matching: We develop randomized algorithms to show that (1 + ε)-approximate matching in regular graphs is truly local, i.e., the locality depends only on ε and is independent of all other graph parameters. Furthermore, as long as the degree Δ is not very small (namely, as long as Δ ≥ poly(1/ε)), this dependence is only logarithmic in 1/ε. This stands in sharp contrast to maximal matching in regular graphs which requires some dependence on the number of nodes n or the degree Δ. 2) Maximal matching: Our techniques further allow us to establish a strong separation between the node-averaged complexity and worst-case complexity of maximal matching in regular graphs, by showing that the former is only O(1). Central to our main technical contribution is a novel martingale-based analysis for the ≈ 40-year-old algorithm by Luby. In particular, our analysis shows that applying one round of Luby’s algorithm on the line graph of a Δ-regular graph results in an almost Δ/2-regular graph.
Cite as

Seri Khoury, Manish Purohit, Aaron Schild, and Joshua R. Wang. On the Randomized Locality of Matching Problems in Regular Graphs. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 40:1-40:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{khoury_et_al:LIPIcs.DISC.2025.40,
  author =	{Khoury, Seri and Purohit, Manish and Schild, Aaron and Wang, Joshua R.},
  title =	{{On the Randomized Locality of Matching Problems in Regular Graphs}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{40:1--40:20},
  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.40},
  URN =		{urn:nbn:de:0030-drops-248570},
  doi =		{10.4230/LIPIcs.DISC.2025.40},
  annote =	{Keywords: regular graphs, maximum matching, augmenting paths, distributed algorithms, Luby’s algorithm, martingales}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.108
Deterministic Approximation Algorithm for Graph Burning

Authors: Matej Lieskovský

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

Abstract
Graph Burning models a contagion spreading in a network as a process such that in each step one node is infected and also the infection spreads to all neighbors of previously infected nodes. Formally, the burning number b(G) of a given graph G = (V,E), possibly with edge lengths, is the minimum number g such that there exists a sequence of nodes v₁,…,v_g satisfying the property that for each w ∈ V there exists i ∈ {1,…,g} so that the distance between w and v_i is at most g-i. We present an elegant deterministic 2.314-approximation algorithm for the Graph Burning problem on general graphs with arbitrary edge lengths. This algorithm matches the approximation ratio of the previous randomized 2.314-approximation algorithm and improves on the previous deterministic 3-approximation algorithm.
Cite as

Matej Lieskovský. Deterministic Approximation Algorithm for Graph Burning. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 108:1-108:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lieskovsky:LIPIcs.ESA.2025.108,
  author =	{Lieskovsk\'{y}, Matej},
  title =	{{Deterministic Approximation Algorithm for Graph Burning}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{108:1--108:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.108},
  URN =		{urn:nbn:de:0030-drops-245775},
  doi =		{10.4230/LIPIcs.ESA.2025.108},
  annote =	{Keywords: Graph Algorithms, Approximation Algorithms, Graph Burning}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.27
Cops and Robbers for Graphs on Surfaces with Crossings

Authors: Prosenjit Bose, Pat Morin, and Karthik Murali

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

Abstract
Cops and Robbers is a game played on a graph where a set of cops attempt to capture a single robber. The game proceeds in rounds, where each round first consists of the cops' turn, followed by the robber’s turn. In the first round, the cops place themselves on a subset of vertices, after which the robber chooses a vertex to place himself. From the next round onwards, in the cops' turn, every cop can choose to either stay on the same vertex or move to an adjacent vertex, and likewise the robber in his turn. The robber is considered to be captured if, at any point in time, there is some cop on the same vertex as the robber. The cops win if they can capture the robber within a finite number of rounds; else the robber wins. A natural question in this game concerns the cop-number of a graph - the minimum number of cops needed to capture a robber. It has long been known that graphs embeddable (without crossings) on surfaces of bounded genus have bounded cop-number. In contrast, it was shown recently that the class of 1-planar graphs - graphs that can be drawn on the plane with at most one crossing per edge - does not have bounded cop-number. This paper initiates an investigation into how the distance between crossing pairs of edges influences a graph’s cop number. In particular, we look at Distance d Cops and Robbers, a variant of the classical game, where the robber is considered to be captured if there is a cop within distance d of the robber. Let c_d(G) denote the minimum number of cops required in the graph G to capture a robber within distance d. We look at various classes of graphs, such as 1-plane graphs, k-plane graphs (graphs where each edge is crossed at most k times), and even general graph drawings, and show that if every crossing pair of edges can be connected by a path of small length, then c_d(G) is bounded, for small values of d. For example, we show that if a graph G admits a drawing in which every pair of crossing edges is contained in a path of length at most 3, then c₄(G) ≤ 21. And if the drawing permits a stronger assumption that the endpoints of every crossing induce the complete graph K₄, then c₃(G) ≤ 9. The tools and techniques that we develop in this paper are sufficiently general, enabling us to examine graphs drawn not only on the sphere but also on orientable and non-orientable surfaces.
Cite as

Prosenjit Bose, Pat Morin, and Karthik Murali. Cops and Robbers for Graphs on Surfaces with Crossings. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bose_et_al:LIPIcs.MFCS.2025.27,
  author =	{Bose, Prosenjit and Morin, Pat and Murali, Karthik},
  title =	{{Cops and Robbers for Graphs on Surfaces with Crossings}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{27:1--27: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.27},
  URN =		{urn:nbn:de:0030-drops-241349},
  doi =		{10.4230/LIPIcs.MFCS.2025.27},
  annote =	{Keywords: Cops and Robbers, Crossings, 1-Planar, Surfaces}
}
Document
Research
DOI: 10.4230/OASIcs.Grossi.4
On Graph Burning and Edge Burning

Authors: Giuseppe F. Italiano, Athanasios L. Konstantinidis, and Manas Jyoti Kashyop

Published in: OASIcs, Volume 132, From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday (2025)

Abstract
Graph burning is a deterministic, discrete-time process that models how influence or contagion spreads in a graph. Initially, all vertices are unburned. At each round, one new vertex is chosen to burn. Once a vertex is burned, in the next round each of its unburned neighbors become burned. The process ends when all vertices are burned. The burning number of a graph is the minimum number of rounds needed for the process to end. Very recently, a variant called edge burning was introduced, where instead of vertices we burn edges: at each round one new edge is burned. Once an edge is burned, in the next round all its unburned incident edges become burned. The edge burning number is the minimum number of rounds that are needed to burn all the edges. In this paper, we present a systematic study of edge burning and provide some new results for graph burning. First, we show a tight relationship between the edge burning number and the burning number of a given graph: specifically, their absolute difference is at most 1. Moreover, we show that the edge burning number of a graph is equal to the graph burning number of its line graph. On the computation complexity side, we show that the edge burning problem is NP-complete, but can be solved in linear time on paths, split graphs, and cographs. Furthermore, we give an XP algorithm when the edge burning problem is parameterized by the diameter of the input graph and a linear kernel when parameterized by the neighborhood diversity. For the graph burning problem, we provide 2-approximation algorithms when either the solution is part of the input or forced to form a path.
Cite as

Giuseppe F. Italiano, Athanasios L. Konstantinidis, and Manas Jyoti Kashyop. On Graph Burning and Edge Burning. In From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 132, pp. 4:1-4:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{italiano_et_al:OASIcs.Grossi.4,
  author =	{Italiano, Giuseppe F. and Konstantinidis, Athanasios L. and Kashyop, Manas Jyoti},
  title =	{{On Graph Burning and Edge Burning}},
  booktitle =	{From Strings to Graphs, and Back Again: A Festschrift for Roberto Grossi's 60th Birthday},
  pages =	{4:1--4:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-391-1},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{132},
  editor =	{Conte, Alessio and Marino, Andrea and Rosone, Giovanna and Vitter, Jeffrey Scott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Grossi.4},
  URN =		{urn:nbn:de:0030-drops-238039},
  doi =		{10.4230/OASIcs.Grossi.4},
  annote =	{Keywords: Burning Number, Graph Burning, Edge Burning, Approximation}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.5
Asynchronous Majority Dynamics on Binomial Random Graphs

Authors: Divyarthi Mohan and Paweł Prałat

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

Abstract
We study information aggregation in networks when agents interact to learn a binary state of the world. Initially each agent privately observes an independent signal which is correct with probability 1/2+δ for some δ > 0. At each round, a node is selected uniformly at random to update their public opinion to match the majority of their neighbours (breaking ties in favour of their initial private signal). Our main result shows that for sparse and connected binomial random graphs G(n,p) the process stabilizes in a correct consensus in 𝒪(nlog² n/log log n) steps with high probability. In fact, when log n/n ≪ p = o(1) the process terminates at time T^ = (1+o(1))nlog n, where T^ is the first time when all nodes have been selected at least once. However, in dense binomial random graphs with p = Ω(1), there is an information cascade where the process terminates in the incorrect consensus with probability bounded away from zero.
Cite as

Divyarthi Mohan and Paweł Prałat. Asynchronous Majority Dynamics on Binomial Random Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 5:1-5:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mohan_et_al:LIPIcs.APPROX/RANDOM.2024.5,
  author =	{Mohan, Divyarthi and Pra{\l}at, Pawe{\l}},
  title =	{{Asynchronous Majority Dynamics on Binomial Random Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{5:1--5:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.5},
  URN =		{urn:nbn:de:0030-drops-209985},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.5},
  annote =	{Keywords: Opinion dynamics, Social learning, Stochastic processes, Random Graphs, Consensus}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.29
A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process

Authors: Pu Gao, Calum MacRury, and Paweł Prałat

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

Abstract
The semi-random graph process is a single player game in which the player is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v, and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a Hamiltonian cycle in as few rounds as possible. In particular, we present an adaptive strategy for the player which achieves it in α n rounds, where α < 2.01678 is derived from the solution to some system of differential equations. We also show that the player cannot achieve the desired property in less than β n rounds, where β > 1.26575. These results improve the previously best known bounds and, as a result, the gap between the upper and lower bounds is decreased from 1.39162 to 0.75102.
Cite as

Pu Gao, Calum MacRury, and Paweł Prałat. A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 29:1-29:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.APPROX/RANDOM.2022.29,
  author =	{Gao, Pu and MacRury, Calum and Pra{\l}at, Pawe{\l}},
  title =	{{A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{29:1--29:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.29},
  URN =		{urn:nbn:de:0030-drops-171517},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.29},
  annote =	{Keywords: Random graphs and processes, Online adaptive algorithms, Hamiltonian cycles, Differential equation method}
}
  • Refine by Type
  • 6 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 4 2025
  • 1 2024
  • 1 2022

  • Refine by Author
  • 2 Prałat, Paweł
  • 1 Bose, Prosenjit
  • 1 Gao, Pu
  • 1 Italiano, Giuseppe F.
  • 1 Kashyop, Manas Jyoti
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Probabilistic algorithms
  • 1 Mathematics of computing → Stochastic processes
  • Show More...

  • Refine by Keyword
  • 2 Graph Burning
  • 1 1-Planar
  • 1 Approximation
  • 1 Approximation Algorithms
  • 1 Burning Number
  • 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