×

Constructing tree decompositions of graphs with bounded gonality. (English) Zbl 07336120

Kim, Donghyun (ed.) et al., Computing and combinatorics. 26th international conference, COCOON 2020, Atlanta, GA, USA, August 29–31, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12273, 384-396 (2020).
Summary: In this paper, we give a constructive proof of the fact that the treewidth of a graph is at most its divisorial gonality. The proof gives a polynomial time algorithm to construct a tree decomposition of width at most \(k\), when an effective divisor of degree \(k\) that reaches all vertices is given. We also give a similar result for two related notions: stable divisorial gonality and stable gonality.
For the entire collection see [Zbl 1458.68009].

MSC:

68Rxx Discrete mathematics in relation to computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Baker, M., Specialization of linear systems from curves to graphs, Algebra Number Theor., 2, 6, 613-653 (2008) · Zbl 1162.14018 · doi:10.2140/ant.2008.2.613
[2] Baker, M.; Norine, S., Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math., 215, 2, 766-788 (2007) · Zbl 1124.05049 · doi:10.1016/j.aim.2007.04.012
[3] Baker, M.; Norine, S., Harmonic morphisms and hyperelliptic graphs, Int. Math. Res. Not., 2009, 15, 2914-2955 (2009) · Zbl 1178.05031
[4] Bertele, U.; Brioschi, F., Nonserial Dynamic Programming (1972), New York: Academic Press, New York · Zbl 0244.49007
[5] Bodlaender, HL, A partial \(k\)-arboretum of graphs with bounded treewidth, Theor. Comput. Sci., 209, 1-45 (1998) · Zbl 0912.68148 · doi:10.1016/S0304-3975(97)00228-4
[6] Bodlaender, H.L., van Dobben de Bruyn, J., Gijswijt, D., Smit, H.: Constructing tree decompositions of graphs with bounded gonality . ArXiV e-prints, arXiv:2005.05569 (2020) · Zbl 07336120
[7] Cools, F.; Draisma, J.; Payne, S.; Robeva, E., A tropical proof of the Brill-Noether theorem, Adv. Math., 230, 2, 759-776 (2012) · Zbl 1325.14080 · doi:10.1016/j.aim.2012.02.019
[8] Cornelissen, G.; Kato, F.; Kool, J., A combinatorial Li-Yau inequality and rational points on curves, Math. Ann., 361, 1-2, 211-258 (2015) · Zbl 1341.11034 · doi:10.1007/s00208-014-1067-x
[9] Dhar, D., Self-organized critical state of sandpile automaton models, Phys. Rev. Lett., 64, 14, 1613 (1990) · Zbl 0943.82553 · doi:10.1103/PhysRevLett.64.1613
[10] van Dobben de Bruyn, J., Gijswijt, D.: Treewidth is a lower bound on graph gonality . ArXiV e-prints, arXiv:1407.7055v2 (2014) · Zbl 1477.05125
[11] Hendrey, K., Sparse graphs of high gonality, SIAM J. Discrete Math., 32, 2, 1400-1407 (2018) · Zbl 1388.05105 · doi:10.1137/16M1095329
[12] Robertson, N.; Seymour, PD, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7, 3, 309-322 (1986) · Zbl 0611.05017 · doi:10.1016/0196-6774(86)90023-4
[13] Seymour, PD; Thomas, R., Graph searching and a minimax theorem for tree-width, J. Comb. Theor. Ser. B, 58, 239-257 (1993) · Zbl 0795.05110 · doi:10.1006/jctb.1993.1027
[14] Urakawa, H., A discrete analogue of the harmonic morphism and Green kernel comparison theorems, Glasgow Math. J., 42, 3, 319-334 (2000) · Zbl 1002.05049 · doi:10.1017/S0017089500030019
[15] Goldreich, O.: Foundations of Cryptography - Basic Tools. Cambridge University Press (2001) · Zbl 1007.94016
[16] Goldreich, O.; Krawczyk, H., On the composition of zero-knowledge proof systems, SIAM J. Comput., 25, 1, 169-192 (1996) · Zbl 0841.68112 · doi:10.1137/S0097539791220688
[17] Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: STOC 1987: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pp. 218-229. ACM, New York (1987)
[18] Goldwasser, S.; Micali, S.; Rackoff, C., The knowledge complexity of interactive proof systems, SIAM J. Comput., 18, 1, 186-208 (1989) · Zbl 0677.68062 · doi:10.1137/0218012
[19] Haitner, I.; Holenstein, T.; Reingold, O., On the (im)possibility of key dependent encryption, Theory of Cryptography, 202-219 (2009), Heidelberg: Springer, Heidelberg · Zbl 1213.94105 · doi:10.1007/978-3-642-00457-5_13
[20] Halevi, S.; Myers, S.; Rackoff, C.; Canetti, R., On seed-incompressible functions, Theory of Cryptography, 19-36 (2008), Heidelberg: Springer, Heidelberg · Zbl 1162.94364 · doi:10.1007/978-3-540-78524-8_2
[21] Ishai, Y.; Sahai, A.; Wagner, D.; Boneh, D., Private circuits: securing hardware against probing attacks, Advances in Cryptology - CRYPTO 2003, 463-481 (2003), Heidelberg: Springer, Heidelberg · Zbl 1122.94378 · doi:10.1007/978-3-540-45146-4_27
[22] Katz, J.; Vaikuntanathan, V.; Matsui, M., Signature schemes with bounded leakage resilience, Advances in Cryptology - ASIACRYPT 2009, 703-720 (2009), Heidelberg: Springer, Heidelberg · Zbl 1267.94072 · doi:10.1007/978-3-642-10366-7_41
[23] Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: STOC 2002, pp. 723-732 (1992)
[24] Komargodski, I., Leakage resilient one-way functions: the auxiliary-input setting, Theor. Comput. Sci., 746, 6-18 (2018) · Zbl 1408.94942 · doi:10.1016/j.tcs.2018.06.014
[25] Marcedone, A.; Pass, R.; Shelat, A.; Zikas, V.; De Prisco, R., Bounded KDM security from iO and OWF, Security and Cryptography for Networks, 571-586 (2016), Cham: Springer, Cham · Zbl 1482.94054 · doi:10.1007/978-3-319-44618-9_30
[26] Maurer, UM; Rueppel, RA, Factoring with an oracle, Advances in Cryptology — EUROCRYPT’ 92, 429-436 (1993), Heidelberg: Springer, Heidelberg · Zbl 0799.11061 · doi:10.1007/3-540-47555-9_35
[27] Micali, S.; Reyzin, L.; Naor, M., Physically observable cryptography, Theory of Cryptography, 278-296 (2004), Heidelberg: Springer, Heidelberg · Zbl 1197.94197 · doi:10.1007/978-3-540-24638-1_16
[28] Naor, M.; Boneh, D., On cryptographic assumptions and challenges, Advances in Cryptology - CRYPTO 2003, 96-109 (2003), Heidelberg: Springer, Heidelberg · Zbl 1122.94391 · doi:10.1007/978-3-540-45146-4_6
[29] Nielsen, J.B., Venturi, D., Zottarel, A.: On the connection between leakage tolerance and adaptive security. IACR Cryptology ePrint Archive, 2014:517 (2014) · Zbl 1314.94091
[30] Ostrovsky, R.; Persiano, G.; Visconti, I.; Gennaro, R.; Robshaw, M., Impossibility of black-box simulation against leakage attacks, Advances in Cryptology - CRYPTO 2015, 130-149 (2015), Heidelberg: Springer, Heidelberg · Zbl 1336.94068 · doi:10.1007/978-3-662-48000-7_7
[31] Pass, R.: Limits of provable security from standard assumptions. In: STOC, pp. 109-118 (2011) · Zbl 1288.94080
[32] Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: STOC 1990, pp. 387-394 (1990)
[33] Rothblum, GN; Vadhan, SP, Are PCPS inherent in efficient arguments?, Comput. Complex., 19, 2, 265-304 (2010) · Zbl 1217.68098 · doi:10.1007/s00037-010-0291-3
[34] Wichs, D.: Barriers in cryptography with weak, correlated and leaky sources. In: Innovations in Theoretical Computer Science, ITCS 2013, Berkeley, CA, USA, January 9-12, 2013, pp. 111-126 (2013) · Zbl 1364.94567
[35] Yao, A.C.-C.: How to generate and exchange secrets. In: Proceedings of the 27th Annual Symposium on Foundations of Computer Science (FOCS), pp. 162-167. IEEE Computer Society (1986)
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.