Recognizing hyperelliptic graphs in polynomial time. (English) Zbl 1436.05105
Summary: Based on analogies between algebraic curves and graphs, M. Baker and S. Norine [Int. Math. Res. Not. 2009, No. 15, 2914–2955 (2009; Zbl 1178.05031)] introduced divisorial gonality, a graph parameter for multigraphs related to treewidth, multigraph algorithms and number theory. Various equivalent definitions of the gonality of an algebraic curve translate to different notions of gonality for graphs, called stable gonality and stable divisorial gonality.
We consider so-called hyperelliptic graphs (multigraphs of gonality 2, in any meaning of graph gonality) and provide a safe and complete set of reduction rules for such multigraphs. This results in an algorithm to recognize hyperelliptic graphs in time \(O(m + n \log n)\), where \(n\) is the number of vertices and \(m\) the number of edges of the multigraph. A corollary is that we can decide with the same runtime whether a two-edge-connected graph \(G\) admits an involution \(\sigma\) such that the quotient \(G / \langle \sigma \rangle\) is a tree.
We consider so-called hyperelliptic graphs (multigraphs of gonality 2, in any meaning of graph gonality) and provide a safe and complete set of reduction rules for such multigraphs. This results in an algorithm to recognize hyperelliptic graphs in time \(O(m + n \log n)\), where \(n\) is the number of vertices and \(m\) the number of edges of the multigraph. A corollary is that we can decide with the same runtime whether a two-edge-connected graph \(G\) admits an involution \(\sigma\) such that the quotient \(G / \langle \sigma \rangle\) is a tree.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
Citations:
Zbl 1178.05031References:
| [1] | Amini, Omid; Baker, Matthew; Brugallé, Erwan; Rabinoff, Joseph, Lifting harmonic morphisms II: tropical curves and metrized complexes, Algebra Number Theory, 9, 2, 267-315 (2015) · Zbl 1312.14138 |
| [2] | Arnborg, Stefan; Proskurowski, Andrzej, Characterization and recognition of partial 3-trees, SIAM J. Algebraic Discrete Methods, 7, 2, 305-314 (1986) · Zbl 0597.05027 |
| [3] | Babai, László, Graph isomorphism in quasipolynomial time [extended abstract], (Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing. Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC’16 (2016)), 684-697, extended abstract of · Zbl 1376.68058 |
| [4] | Bak, Per; Tang, Chao; Wiesenfeld, Kurt, Self-organized criticality, Phys. Rev. A, 38, 1, 364 (1988) · Zbl 1230.37103 |
| [5] | Baker, Matthew, Specialization of linear systems from curves to graphs, Algebra Number Theory, 2, 6, 613-653 (2008), with an appendix by Brian Conrad · Zbl 1162.14018 |
| [6] | Baker, Matthew; Norine, Serguei, Harmonic morphisms and hyperelliptic graphs, Int. Math. Res. Not. IMRN, 15, 2914-2955 (2009) · Zbl 1178.05031 |
| [7] | Baker, Matthew; Shokrieh, Farbod, Chip-firing games, potential theory on graphs, and spanning trees, J. Comb. Theory, Ser. A, 120, 1, 164-182 (2013) · Zbl 1408.05089 |
| [8] | Bienstock, Daniel; Seymour, Paul, Monotonicity in graph searching, J. Algorithms, 12, 239-245 (1991) · Zbl 0760.05081 |
| [9] | Björner, Anders; Lovász, László; Shor, Peter W., Chip-firing games on graphs, Eur. J. Comb., 12, 4, 283-291 (1991) · Zbl 0729.05048 |
| [10] | Bodewes, Jelco M.; Bodlaender, Hans L.; Cornelissen, Gunther; van der Wegen, Marieke, Recognizing hyperelliptic graphs in polynomial time [extended abstract], (Brandstädt, Andreas; Köhler, Ekkehard; Meer, Klaus, Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, WG 2018. Graph-Theoretic Concepts in Computer Science. Graph-Theoretic Concepts in Computer Science, WG 2018, Springer Lecture Notes in Computer Science, vol. 11159 (2018)), 52-64 · Zbl 1517.68276 |
| [11] | Bodlaender, Hans L.; Drange, Pål Grønås; Dregi, Markus S.; Fomin, Fedor V.; Lokshtanov, Daniel; Pilipczuk, Michał, A \(c^k n 5\)-approximation algorithm for treewidth, SIAM J. Comput., 45, 2, 317-378 (2016) · Zbl 1333.05282 |
| [12] | Bodlaender, Hans L.; Hagerup, Torben, Parallel algorithms with optimal speedup for bounded treewidth, SIAM J. Comput., 27, 6, 1725-1746 (1998) · Zbl 0907.68089 |
| [13] | Bodlaender, Hans L.; Koster, Arie M. C.A., Treewidth computations II. Lower bounds, Inf. Comput., 209, 7, 1103-1119 (2011) · Zbl 1220.68071 |
| [14] | Bodlaender, Hans L.; van der Wegen, Marieke; van der Zanden, Tom C., Stable divisorial gonality is in NP [extended abstract], (Catania, Barbara; Královič, Rastislav; Nawrocki, Jerzy; Pighizzini, Giovanni, SOFSEM 2019: Theory and Practice of Computer Science. SOFSEM 2019: Theory and Practice of Computer Science, SOFSEM 2019. SOFSEM 2019: Theory and Practice of Computer Science. SOFSEM 2019: Theory and Practice of Computer Science, SOFSEM 2019, Springer Lecture Notes in Computer Science, vol. 11376 (2019)), 81-93, extended abstract of · Zbl 1444.68138 |
| [15] | Bosma, Wieb; Cannon, John; Playoust, Catherine, The Magma algebra system. I. The user language, J. Symb. Comput., 24, 3-4, 235-265 (1997) · Zbl 0898.68039 |
| [16] | Chan, Melody; Glass, Darren; Macauley, Matthew; Perkinson, David; Werner, Caryn; Yang, Qiaoyu, Sandpiles, spanning trees, and plane duality, SIAM J. Discrete Math., 29, 1, 461-471 (2015) · Zbl 1327.05342 |
| [17] | Cohen, Henri; Frey, Gerhard; Avanzi, Roberto; Doche, Christophe; Lange, Tanja; Nguyen, Kim; Vercauteren, Frederik, Handbook of Elliptic and Hyperelliptic Curve Cryptography (2012), Chapman & Hall/CRC · Zbl 1082.94001 |
| [18] | Cornelissen, Gunther; Kato, Fumiharu; Kool, Janne, A combinatorial Li-Yau inequality and rational points on curves, Math. Ann., 361, 1-2, 211-258 (2015) · Zbl 1341.11034 |
| [19] | Courcelle, Bruno, The monadic second-order logic of graphs. I: Recognizable sets of finite graphs, Inf. Comput., 85, 1, 12-75 (1990) · Zbl 0722.03008 |
| [20] | Dhar, Deepak, Self-organized critical state of sandpile automaton models, Phys. Rev. Lett., 64, 14, 1613 (1990) · Zbl 0943.82553 |
| [21] | van Dobben de Bruyn, Josse, Reduced divisors and gonality in finite graphs (2012), Leiden University, Bachelor thesis |
| [22] | van Dobben de Bruyn, Josse; Gijswijt, Dion, Treewidth is a lower bound on graph gonality (2014), preprint · Zbl 1477.05125 |
| [23] | Dutta, Neelav; Jensen, David, Gonality of expander graphs, Discrete Math., 341, 9, 2535-2543 (2018) · Zbl 1392.05099 |
| [24] | Gijswijt, Dion; Smit, Harry; van der Wegen, Marieke, Computing graph gonality is hard (2019), preprint · Zbl 1450.05088 |
| [25] | Groot Koerkamp, Ragnar; van der Wegen, Marieke, Stable gonality is computable, Discret. Math. Theor. Comput. Sci., 21, 1 (2019), ICGT 2018 · Zbl 1417.05234 |
| [26] | Hagerup, Torben, Dynamic algorithms for graphs of bounded treewidth, Algorithmica, 27, 3, 292-315 (2000) · Zbl 0959.03019 |
| [27] | Helfgott, Harald Andrés, Isomorphismes de graphes en temps quasi-polynomial [d’après Babai et Luks, Weisfeiler-Leman,…], (Séminaire Bourbaki. Vol. 2016/2017. Exposés 1120-1135. Séminaire Bourbaki. Vol. 2016/2017. Exposés 1120-1135, Astérisque, vol. 407:Exp. No. 1125 (2019)), 135-182 · Zbl 1483.05181 |
| [28] | Hendrey, Kevin, Sparse graphs of high gonality, SIAM J. Discrete Math., 32, 2, 1400-1407 (2018) · Zbl 1388.05105 |
| [29] | LaPaugh, Andrea S., Recontamination does not help to search a graph, J. ACM, 40, 2, 224-245 (April 1993) · Zbl 0768.68048 |
| [30] | Lubiw, Anna, Some NP-complete problems similar to graph isomorphism, SIAM J. Comput., 10, 1, 11-21 (1981) · Zbl 0454.68025 |
| [31] | Norin, Sergey, New tools and results in graph minor structure theory, (Surveys in Combinatorics 2015. Surveys in Combinatorics 2015, London Math. Soc. Lecture Note Ser., vol. 424 (2015), Cambridge Univ. Press), 221-260 · Zbl 1352.05172 |
| [32] | Poonen, Bjorn, Computing rational points on curves, (Number Theory for the Millennium, III. Number Theory for the Millennium, III, Urbana, IL, 2000 (2002), A K Peters: A K Peters Natick, MA), 149-172 · Zbl 1038.11037 |
| [33] | Schicho, Josef; Schreyer, Frank-Olaf; Weimann, Martin, Computational aspects of gonal maps and radical parametrization of curves, Appl. Algebra Eng. Commun. Comput., 24, 5, 313-341 (2013) · Zbl 1299.14047 |
| [34] | Tardos, Gábor, Polynomial bound for a chip firing game on graphs, SIAM J. Discrete Math., 1, 3, 397-398 (1988) · Zbl 0652.68089 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
