Search Results

Documents authored by Suppakitpaisarn, Vorapong

Document
DOI: 10.4230/LIPIcs.STACS.2025.49
Cycle Counting Under Local Differential Privacy for Degeneracy-Bounded Graphs

Authors: Quentin Hillebrand, Vorapong Suppakitpaisarn, and Tetsuo Shibuya

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We propose an algorithm for counting the number of cycles under local differential privacy for degeneracy-bounded input graphs. Numerous studies have focused on counting the number of triangles under the privacy notion, demonstrating that the expected 𝓁₂-error of these algorithms is Ω(n^{1.5}), where n is the number of nodes in the graph. When parameterized by the number of cycles of length four (C₄), the best existing triangle counting algorithm has an error of O(n^{1.5} + √C₄) = O(n²). In this paper, we introduce an algorithm with an expected 𝓁₂-error of O(δ^1.5 n^0.5 + δ^0.5 d_max^0.5 n^0.5), where δ is the degeneracy and d_{max} is the maximum degree of the graph. For degeneracy-bounded graphs (δ ∈ Θ(1)) commonly found in practical social networks, our algorithm achieves an expected 𝓁₂-error of O(d_{max}^{0.5} n^{0.5}) = O(n). Our algorithm’s core idea is a precise count of triangles following a preprocessing step that approximately sorts the degree of all nodes. This approach can be extended to approximate the number of cycles of length k, maintaining a similar 𝓁₂-error, namely O(δ^{(k-2)/2} d_max^0.5 n^{(k-2)/2} + δ^{k/2} n^{(k-2)/2}) or O(d_max^0.5 n^{(k-2)/2}) = O(n^{(k-1)/2}) for degeneracy-bounded graphs.
Cite as

Quentin Hillebrand, Vorapong Suppakitpaisarn, and Tetsuo Shibuya. Cycle Counting Under Local Differential Privacy for Degeneracy-Bounded Graphs. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 49:1-49:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hillebrand_et_al:LIPIcs.STACS.2025.49,
  author =	{Hillebrand, Quentin and Suppakitpaisarn, Vorapong and Shibuya, Tetsuo},
  title =	{{Cycle Counting Under Local Differential Privacy for Degeneracy-Bounded Graphs}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{49:1--49:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine 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.2025.49},
  URN =		{urn:nbn:de:0030-drops-228748},
  doi =		{10.4230/LIPIcs.STACS.2025.49},
  annote =	{Keywords: Differential privacy, triangle counting, degeneracy, arboricity, graph theory, parameterized accuracy}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2023.10
Submodularity Property for Facility Locations of Dynamic Flow Networks

Authors: Peerawit Suriya, Vorapong Suppakitpaisarn, Supanut Chaidee, and Phapaengmueng Sukkasem

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract
This paper considers facility location problems within dynamic flow networks, shifting the focus from minimizing evacuation time to handling situations with a constrained evacuation timeframe. Our study sets two main goals: 1) Determining a fixed-size set of locations that can maximize the number of evacuees, and 2) Identifying the smallest set of locations capable of accommodating all evacuees within the time constraint. We introduce flow_t(S) to represent the number of evacuees for given locations S within a fixed time limit t. We prove that flow_t functions is a monotone submodular function, which allows us to apply an approximation algorithm specifically designed for maximizing such functions with size restrictions. For the second objective, we implement an approximation algorithm tailored to solving the submodular cover problem. We conduct experiments on the real datasets of Chiang Mai, and demonstrate that the approximation algorithms give solutions which are close to optimal for all of the experiments we have conducted.
Cite as

Peerawit Suriya, Vorapong Suppakitpaisarn, Supanut Chaidee, and Phapaengmueng Sukkasem. Submodularity Property for Facility Locations of Dynamic Flow Networks. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{suriya_et_al:OASIcs.ATMOS.2023.10,
  author =	{Suriya, Peerawit and Suppakitpaisarn, Vorapong and Chaidee, Supanut and Sukkasem, Phapaengmueng},
  title =	{{Submodularity Property for Facility Locations of Dynamic Flow Networks}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{10:1--10:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.10},
  URN =		{urn:nbn:de:0030-drops-187711},
  doi =		{10.4230/OASIcs.ATMOS.2023.10},
  annote =	{Keywords: Approximation Algorithms, Dynamic Networks, Facility Location, Submodular Function Optimization}
}
Document
PACE Solver Description
DOI: 10.4230/LIPIcs.IPEC.2020.31
PACE Solver Description: Computing Exact Treedepth via Minimal Separators

Authors: Zijian Xu, Dejun Mao, and Vorapong Suppakitpaisarn

Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Abstract
This is a description of team xuzijian629’s treedepth solver submitted to PACE 2020. As we use a top-down approach, we enumerate all possible minimal separators at each step. The enumeration is sped up by several novel pruning techniques and is based on our conjecture that we can always have an optimal decomposition without using separators with size larger than treewidth. Although we cannot theoretically guarantee that our algorithm based on the unproved conjecture can always give an optimal solution, it can give optimal solutions for all instances in our experiments. The algorithm solved 68 private instances and placed 5th in the competition.
Cite as

Zijian Xu, Dejun Mao, and Vorapong Suppakitpaisarn. PACE Solver Description: Computing Exact Treedepth via Minimal Separators. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 31:1-31:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{xu_et_al:LIPIcs.IPEC.2020.31,
  author =	{Xu, Zijian and Mao, Dejun and Suppakitpaisarn, Vorapong},
  title =	{{PACE Solver Description: Computing Exact Treedepth via Minimal Separators}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{31:1--31:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Cao, Yixin and Pilipczuk, Marcin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.31},
  URN =		{urn:nbn:de:0030-drops-133340},
  doi =		{10.4230/LIPIcs.IPEC.2020.31},
  annote =	{Keywords: Treedepth, Minimal Separators, Experimental Algorithm}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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