Search Results

Documents authored by Krohmer, Anton

Document
DOI: 10.4230/LIPIcs.ESA.2017.37
Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT

Authors: Tobias Friedrich, Anton Krohmer, Ralf Rothenberger, Thomas Sauerwald, and Andrew M. Sutton

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. The worst-case hardness of SAT lies at the core of computational complexity theory. The average-case analysis of SAT has triggered the development of sophisticated rigorous and non-rigorous techniques for analyzing random structures. Despite a long line of research and substantial progress, nearly all theoretical work on random SAT assumes a uniform distribution on the variables. In contrast, real-world instances often exhibit large fluctuations in variable occurrence. This can be modeled by a scale-free distribution of the variables, which results in distributions closer to industrial SAT instances. We study random k-SAT on n variables, m = Theta(n) clauses, and a power law distribution on the variable occurrences with exponent beta. We observe a satisfiability threshold at beta = (2k-1)/(k-1). This threshold is tight in the sense that instances with beta <= (2k-1)/(k-1)-epsilon for any constant epsilon > 0 are unsatisfiable with high probability (w.h.p.). For beta >= (2k-1)/(k-1)+epsilon, the picture is reminiscent of the uniform case: instances are satisfiable w.h.p. for sufficiently small constant clause-variable ratios m/n; they are unsatisfiable above a ratio m/n that depends on beta.
Cite as

Tobias Friedrich, Anton Krohmer, Ralf Rothenberger, Thomas Sauerwald, and Andrew M. Sutton. Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{friedrich_et_al:LIPIcs.ESA.2017.37,
  author =	{Friedrich, Tobias and Krohmer, Anton and Rothenberger, Ralf and Sauerwald, Thomas and Sutton, Andrew M.},
  title =	{{Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.37},
  URN =		{urn:nbn:de:0030-drops-78356},
  doi =		{10.4230/LIPIcs.ESA.2017.37},
  annote =	{Keywords: satisfiability, random structures, random SAT, power law distribution, scale-freeness, phase transitions}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.15
Hyperbolic Random Graphs: Separators and Treewidth

Authors: Thomas Bläsius, Tobias Friedrich, and Anton Krohmer

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
Hyperbolic random graphs share many common properties with complex real-world networks; e.g., small diameter and average distance, large clustering coefficient, and a power-law degree sequence with adjustable exponent beta. Thus, when analyzing algorithms for large networks, potentially more realistic results can be achieved by assuming the input to be a hyperbolic random graph of size n. The worst-case run-time is then replaced by the expected run-time or by bounds that hold with high probability (whp), i.e., with probability 1-O(1/n). Though many structural properties of hyperbolic random graphs have been studied, almost no algorithmic results are known. Divide-and-conquer is an important algorithmic design principle that works particularly well if the instance admits small separators. We show that hyperbolic random graphs in fact have comparatively small separators. More precisely, we show that they can be expected to have balanced separator hierarchies with separators of size O(n^{3/2-beta/2}), O(log n), and O(1) if 2 < beta < 3, beta = 3, and 3 < beta, respectively. We infer that these graphs have whp a treewidth of O(n^{3/2-beta/2}), O(log^2 n), and O(log n), respectively. For 2 < \beta < 3, this matches a known lower bound. To demonstrate the usefulness of our results, we give several algorithmic applications.
Cite as

Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. Hyperbolic Random Graphs: Separators and Treewidth. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.ESA.2016.15,
  author =	{Bl\"{a}sius, Thomas and Friedrich, Tobias and Krohmer, Anton},
  title =	{{Hyperbolic Random Graphs: Separators and Treewidth}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.15},
  URN =		{urn:nbn:de:0030-drops-63667},
  doi =		{10.4230/LIPIcs.ESA.2016.15},
  annote =	{Keywords: hyperbolic random graphs, scale-free networks, power-law graphs, separators, treewidth}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.16
Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane

Authors: Thomas Bläsius, Tobias Friedrich, Anton Krohmer, and Sören Laue

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
Hyperbolic geometry appears to be intrinsic in many large real networks. We construct and implement a new maximum likelihood estimation algorithm that embeds scale-free graphs in the hyperbolic space. All previous approaches of similar embedding algorithms require a runtime of Omega(n^2). Our algorithm achieves quasilinear runtime, which makes it the first algorithm that can embed networks with hundreds of thousands of nodes in less than one hour. We demonstrate the performance of our algorithm on artificial and real networks. In all typical metrics like Log-likelihood and greedy routing our algorithm discovers embeddings that are very close to the ground truth.
Cite as

Thomas Bläsius, Tobias Friedrich, Anton Krohmer, and Sören Laue. Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.ESA.2016.16,
  author =	{Bl\"{a}sius, Thomas and Friedrich, Tobias and Krohmer, Anton and Laue, S\"{o}ren},
  title =	{{Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.16},
  URN =		{urn:nbn:de:0030-drops-63670},
  doi =		{10.4230/LIPIcs.ESA.2016.16},
  annote =	{Keywords: hyperbolic random graphs, embedding, power-law graphs, hyperbolic plane}
}
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