2 Search Results for "Focke, Jacob"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.91
On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order

Authors: J. A. Gregor Lagodzinski, Andreas Göbel, Katrin Casel, and Tobias Friedrich

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We study the problem of counting the number of homomorphisms from an input graph G to a fixed (quantum) graph ̄{H} in any finite field of prime order ℤ_p. The subproblem with graph H was introduced by Faben and Jerrum [ToC'15] and its complexity is still uncharacterised despite active research, e.g. the very recent work of Focke, Goldberg, Roth, and Zivný [SODA'21]. Our contribution is threefold. First, we introduce the study of quantum graphs to the study of modular counting homomorphisms. We show that the complexity for a quantum graph ̄{H} collapses to the complexity criteria found at dimension 1: graphs. Second, in order to prove cases of intractability we establish a further reduction to the study of bipartite graphs. Lastly, we establish a dichotomy for all bipartite (K_{3,3}$1{e}, {domino})-free graphs by a thorough structural study incorporating both local and global arguments. This result subsumes all results on bipartite graphs known for all prime moduli and extends them significantly. Even for the subproblem with p = 2 this establishes new results.
Cite as

J. A. Gregor Lagodzinski, Andreas Göbel, Katrin Casel, and Tobias Friedrich. On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 91:1-91:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lagodzinski_et_al:LIPIcs.ICALP.2021.91,
  author =	{Lagodzinski, J. A. Gregor and G\"{o}bel, Andreas and Casel, Katrin and Friedrich, Tobias},
  title =	{{On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{91:1--91:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.91},
  URN =		{urn:nbn:de:0030-drops-141608},
  doi =		{10.4230/LIPIcs.ICALP.2021.91},
  annote =	{Keywords: Algorithms, Theory, Quantum Graphs, Bipartite Graphs, Graph Homomorphisms, Modular Counting, Complexity Dichotomy}
}
Document
DOI: 10.4230/LIPIcs.SEA.2017.22
Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments

Authors: Jacob Focke, Nicole Megow, and Julie Meißner

Published in: LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017)

Abstract
We consider the minimum spanning tree (MST) problem in an uncertainty model where uncertain edge weights can be explored at extra cost. The task is to find an MST by querying a minimum number of edges for their exact weight. This problem has received quite some attention from the algorithms theory community. In this paper, we conduct the first practical experiments for MST under uncertainty, theoretically compare three known algorithms, and compare theoretical with practical behavior of the algorithms. Among others, we observe that the average performance and the absolute number of queries are both far from the theoretical worst-case bounds. Furthermore, we investigate a known general preprocessing procedure and develop an implementation thereof that maximally reduces the data uncertainty. We also characterize a class of instances that is solved completely by our preprocessing. Our experiments are based on practical data from an application in telecommunications and uncertainty instances generated from the standard TSPLib graph library.
Cite as

Jacob Focke, Nicole Megow, and Julie Meißner. Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{focke_et_al:LIPIcs.SEA.2017.22,
  author =	{Focke, Jacob and Megow, Nicole and Mei{\ss}ner, Julie},
  title =	{{Minimum Spanning Tree under Explorable Uncertainty in Theory and Experiments}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Iliopoulos, Costas S. and Pissis, Solon P. and Puglisi, Simon J. and Raman, Rajeev},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.22},
  URN =		{urn:nbn:de:0030-drops-76202},
  doi =		{10.4230/LIPIcs.SEA.2017.22},
  annote =	{Keywords: MST, explorable uncertainty, competitive ratio, experimental algorithms}
}
  • Refine by Author
  • 1 Casel, Katrin
  • 1 Focke, Jacob
  • 1 Friedrich, Tobias
  • 1 Göbel, Andreas
  • 1 Lagodzinski, J. A. Gregor
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Algorithms
  • 1 Bipartite Graphs
  • 1 Complexity Dichotomy
  • 1 Graph Homomorphisms
  • 1 MST
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2017
  • 1 2021

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 Imprint Privacy Contact