On Hypergraph Supports.

Rajiv Raman; Karamjeet Singh

doi:10.5817/CZ.MUNI.EUROCOMB23-107

On Hypergraph Supports.

EUROCOMB’23

Rajiv Raman Karamjeet Singh

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-107

PDF

Abstract

Let $\mathcal{H}=(X,\mathcal{E})$ be a hypergraph. A support is a graph $Q$ on $X$ such that for each $E\in\mathcal{E}$, the subgraph of $Q$ on the elements in $E$ is connected. We consider hypergraphs defined on a host graph. Given a graph $G=(V,E)$, with $c:V\to\{\mathbf{r},\mathbf{b}\}$ and a collection of connected subgraphs $\mathcal{H}$ of $G$, a primal support is a graph $Q$ on $\mathbf{b}(V)$ such that for each $H\in \mathcal{H}$, the subgraph $Q[\mathbf{b}(H)]$ on vertices $\mathbf{b}(H)=H\cap c^{-1}(\mathbf{b})$ is connected. A dual support is a graph $Q^*$ on $\mathcal{H}$ s.t. for each $v\in X$, the subgraph $Q^*[\mathcal{H}_v]$ is connected, where $\mathcal{H}_v=\{H\in\mathcal{H}: v\in H\}$. We present sufficient conditions on the host graph and hyperedges so that the resulting support comes from a restricted family. We primarily study two classes of graphs: $(1)$ If the host graph has genus $g$ and the hypergraphs satisfy a topological condition of being cross-free, then there is a primal and a dual support of genus at most $g$. $(2)$ If the host graph has treewidth $t$ and the hyperedges satisfy a combinatorial condition of being non-piercing, then there exist primal and dual supports of treewidth $O(2^t)$. We show that this exponential blow-up is sometimes necessary. As an intermediate case, we also study the case when the host graph is outerplanar. Finally, we show applications of our results to packing and covering, and coloring problems on geometric hypergraphs.

Pages:
774–783

References

Eyal Ackerman, Balázs Keszegh, and Dömötör Pálvölgyi. Coloring hypergraphs de- fined by stabbed pseudo-disks and abab-free hypergraphs. SIAM Journal on Discrete Mathematics, 34(4):2250-2269, 2020.
https://doi.org/10.1137/19M1290231

Emmanuelle Anceaume, Maria Gradinariu, Ajoy Kumar Datta, Gwendal Simon, and Antonino Virgillito. A semantic overlay for self-peer-to-peer publish/subscribe. In 26th IEEE International Conference on Distributed Computing Systems (ICDCS'06), pages 22-22. IEEE, 2006.

Daniel Antunes, Claire Mathieu, and Nabil H. Mustafa. Combinatorics of local search: An optimal 4-local hall's theorem for planar graphs. In 25th Annual European Sympo- sium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria, pages 8:1-8:13, 2017.

Roberto Baldoni, Roberto Beraldi, Vivien Quema, Leonardo Querzoni, and Sara Tucci-Piergiovanni. Tera: topic-based event routing for peer-to-peer architectures. In Proceedings of the 2007 inaugural international conference on Distributed event-based systems, pages 2-13, 2007.
https://doi.org/10.1145/1266894.1266898

Roberto Baldoni, Roberto Beraldi, Leonardo Querzoni, and Antonino Virgillito. Ef- ficient publish/subscribe through a self-organizing broker overlay and its application to siena. The Computer Journal, 50(4):444-459, 2007.
https://doi.org/10.1093/comjnl/bxm002

Aniket Basu Roy, Sathish Govindarajan, Rajiv Raman, and Saurabh Ray. Packing and covering with non-piercing regions. Discrete & Computational Geometry, 2018.
https://doi.org/10.1007/s00454-018-9983-2

Sergey Bereg, Krzysztof Fleszar, Philipp Kindermann, Sergey Pupyrev, Joachim Spo- erhase, and Alexander Wolff. Colored non-crossing euclidean steiner forest. In Al- gorithms and Computation: 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings, pages 429-441. Springer, 2015.
https://doi.org/10.1007/978-3-662-48971-0_37

Sergey Bereg, Minghui Jiang, Boting Yang, and Binhai Zhu. On the red/blue spanning tree problem. Theoretical computer science, 412(23):2459-2467, 2011.
https://doi.org/10.1016/j.tcs.2010.10.038

Ulrik Brandes, Sabine Cornelsen, Barbara Pampel, and Arnaud Sallaberry. Blocks of hypergraphs: applied to hypergraphs and outerplanarity. In Combinatorial Algo- rithms: 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers 21, pages 201-211. Springer, 2011.
https://doi.org/10.1007/978-3-642-19222-7_21

Ulrik Brandes, Sabine Cornelsen, Barbara Pampel, and Arnaud Sallaberry. Path- based supports for hypergraphs. Journal of Discrete Algorithms, 14:248-261, 2012.
https://doi.org/10.1016/j.jda.2011.12.009

Kevin Buchin, Marc J van Kreveld, Henk Meijer, Bettina Speckmann, and KAB Verbeek. On planar supports for hypergraphs. Journal of Graph Algorithms and Applications, 15(4):533-549, 2011.
https://doi.org/10.7155/jgaa.00237

Raphaël Chand and Pascal Felber. Semantic peer-to-peer overlays for pub- lish/subscribe networks. In Euro-Par 2005 Parallel Processing: 11th International Euro-Par Conference, Lisbon, Portugal, August 30-September 2, 2005. Proceedings 11, pages 1194-1204. Springer, 2005.
https://doi.org/10.1007/11549468_130

Vincent Cohen-Addad and Claire Mathieu. Effectiveness of local search for geometric optimization. In Proceedings of the Thirty-first International Symposium on Com- putational Geometry, SoCG '15, pages 329-343, Dagstuhl, Germany, 2015. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

Reinhard Diestel. Graph theory 3rd ed. Graduate texts in mathematics, 173(33):12,2005.

John R Gilbert, Joan P Hutchinson, and Robert Endre Tarjan. A separator theorem for graphs of bounded genus. Journal of Algorithms, 5(3):391-407, 1984.
https://doi.org/10.1016/0196-6774(84)90019-1

Frédéric Havet, Dorian Mazauric, Viet-Ha Nguyen, and Rémi Watrigant. Overlay- ing a hypergraph with a graph with bounded maximum degree. Discrete Applied Mathematics, 319:394-406, 2022.
https://doi.org/10.1016/j.dam.2022.05.022

Jun Hosoda, Juraj Hromkovič, Taisuke Izumi, Hirotaka Ono, Monika Steinová, and Koichi Wada. On the approximability and hardness of minimum topic connected overlay and its special instances. Theoretical Computer Science, 429:144-154, 2012.
https://doi.org/10.1016/j.tcs.2011.12.033

Ferran Hurtado, Matias Korman, Marc van Kreveld, Maarten Löffler, Vera Sacristán, Akiyoshi Shioura, Rodrigo I Silveira, Bettina Speckmann, and Takeshi Tokuyama. Colored spanning graphs for set visualization. Computational Geometry, 68:262-276, 2018.
https://doi.org/10.1016/j.comgeo.2017.06.006

Chaya Keller and Shakhar Smorodinsky. Conflict-free coloring of intersection graphs of geometric objects. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Sym- posium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 2397-2411, 2018.
https://doi.org/10.1137/1.9781611975031.154

Balázs Keszegh. Coloring intersection hypergraphs of pseudo-disks. Discret. Comput. Geom., 64(3):942-964, 2020.
https://doi.org/10.1007/s00454-019-00142-6

Balázs Keszegh and Dömötör Pálvölgyi. An abstract approach to polychromatic col- oring: shallow hitting sets in aba-free hypergraphs and pseudohalfplanes. Journal of Computational Geometry, 10(1):1-26, 2019.

Ephraim Korach and Michal Stern. The clustering matroid and the optimal clustering tree. Mathematical Programming, 98:385-414, 2003.
https://doi.org/10.1007/s10107-003-0410-x

Erik Krohn, Matt Gibson, Gaurav Kanade, and Kasturi Varadarajan. Guarding ter- rains via local search. Journal of Computational Geometry, 5(1):168-178, 2014.

NabilHMustafa and SaurabhRay. Improved results on geometric hitting set problems. Discrete & Computational Geometry, 44(4):883-895, 2010.
https://doi.org/10.1007/s00454-010-9285-9

Melih Onus and Andréa W Richa. Minimum maximum-degree publish-subscribe over- lay network design. IEEE/ACM Transactions on Networking, 19(5):1331-1343, 2011.
https://doi.org/10.1109/TNET.2011.2144999

Evangelia Pyrga and Saurabh Ray. New existence proofs for ε-nets. In Proceedings of the Twenty-fourth Annual Symposium on Computational Geometry, SoCG '08, pages 199-207, New York, NY, USA, 2008. ACM.
https://doi.org/10.1145/1377676.1377708

Rajiv Raman and Saurabh Ray. Constructing planar support for non-piercing regions. Discrete & Computational Geometry, 64(3):1098-1122, 2020.
https://doi.org/10.1007/s00454-020-00216-w

AA Voloshina and VZ Feinberg. Planarity of hypergraphs. In DOKLADY AKADEMII NAUK BELARUSI, volume 28, pages 309-311. ACADEMII NAUK BELARUSI F SCORINA PR 66, ROOM 403, MINSK, BYELARUS 220072, 1984.

Eric W Weisstein. Torus grid graph. https://mathworld. wolfram. com/, 2016.

Metrics

0

Views

0

PDF views

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

PDF

European Conference on Combinatorics, Graph Theory and Applications

EUROCOMB'23

On Hypergraph Supports.

EUROCOMB’23

0

0