nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

A Contraction Tree SAT Encoding for Computing Twin-Width

verfasst von : Yinon Horev, Shiraz Shay, Sarel Cohen, Tobias Friedrich, Davis Issac, Lior Kamma, Aikaterini Niklanovits, Kirill Simonov

Erschienen in: Advances in Knowledge Discovery and Data Mining

Verlag: Springer Nature Singapore

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Twin-width is a structural width parameter and matrix invariant introduced by Bonnet et al. [FOCS 2020], that has been gaining attention due to its various fields of applications. In this paper, inspired by the SAT approach of Schidler and Szeider [ALENEX 2022], we provide a new SAT encoding for computing twin-width. The encoding aims to encode the contraction sequence as a binary tree. The asymptotic size of the formula under our encoding is smaller than in the state-of-the-art relative encoding of Schidler and Szeider. We also conduct an experimental study, comparing the performance of the new encoding and the relative encoding.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel GraphNILM: A Graph Neural Network for Energy Disaggregation

PACE stands for Parameterized Algorithms and Computational Experiments; the challenge is dedicated to bringing the gap between theoretical and practical parameterized algorithms. The official website of the challenge is https://pacechallenge.org/2023/.

https://pacechallenge.org/2023/tiny-set.pdf.

All instances are available at https://pacechallenge.org/2023/.

Balabán, J., Hliněný, P.: Twin-width is linear in the Poset width. In: Golovach, P.A., Zehavi, M. (eds.) 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 214, pp. 6:1–6:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl (2021). https://doi.org/10.4230/LIPIcs.IPEC.2021.6

Bergé, P., Bonnet, É., Déprés, H.: Deciding twin-width at most 4 is np-complete. In: Bojanczyk, M., Merelli, E., Woodruff, D.P. (eds.) 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, 4–8 July 2022, Paris. LIPIcs, vol. 229, pp. 18:1–18:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). https://doi.org/10.4230/LIPIcs.ICALP.2022.18

Bonnet, E., Déprés, H.: Twin-width can be exponential in treewidth. J. Comb. Theory Ser. B 161(C), 1–14 (2023). https://doi.org/10.1016/j.jctb.2023.01.003

Bonnet, É., Geniet, C., Kim, E.J., Thomassé, S., Watrigant, R.: Twin-width II: small classes. In: Marx, D. (ed.) Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, 10–13 January 2021, pp. 1977–1996. SIAM (2021). https://doi.org/10.1137/1.9781611976465.118

Bonnet, É., Geniet, C., Kim, E.J., Thomassé, S., Watrigant, R.: Twin-width III: max independent set, min dominating set, and coloring. In: Bansal, N., Merelli, E., Worrell, J. (eds.) 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, 12–16 July 2021, Glasgow (Virtual Conference). LIPIcs, vol. 198, pp. 35:1–35:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021). https://doi.org/10.4230/LIPIcs.ICALP.2021.35

Bonnet, E., Kim, E.J., Reinald, A., Thomassé, S., Watrigant, R.: Twin-width and polynomial kernels. In: Golovach, P.A., Zehavi, M. (eds.) 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), vol. 214, pp. 10:1–10:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl (2021). https://doi.org/10.4230/LIPIcs.IPEC.2021.10

Bonnet, É., Kim, E.J., Thomassé, S., Watrigant, R.: Twin-width I: tractable FO model checking. J. ACM 69(1), 3:1–3:46 (2022). https://doi.org/10.1145/3486655

Ganian, R., Pokrývka, F., Schidler, A., Simonov, K., Szeider, S.: Weighted model counting with twin-width. In: Meel, K.S., Strichman, O. (eds.) 25th International Conference on Theory and Applications of Satisfiability Testing, SAT 2022, 2–5 August 2022, Haifa. LIPIcs, vol. 236, pp. 15:1–15:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022). https://doi.org/10.4230/LIPIcs.SAT.2022.15

Guillemot, S., Marx, D.: Finding small patterns in permutations in linear time. In: Chekuri, C. (ed.) Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, 5–7 January 2014, pp. 82–101. SIAM (2014). https://doi.org/10.1137/1.9781611973402.7

10.

Jacob, H., Pilipczuk, M.: Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs. In: Bekos, M.A., Kaufmann, M. (eds.) Graph-Theoretic Concepts in Computer Science. WG 2022. LNCS, vol. 13453, pp. 287–299. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15914-5_21

11.

Král, D., Lamaison, A.: Planar graph with twin-width seven. arXiv preprint arXiv:2209.11537 (2022)

12.

Král’, D., Lamaison, A.: Planar graph with twin-width seven. Eur. J. Combinator. 103749 (2023). https://doi.org/10.1016/j.ejc.2023.103749

13.

Marques-Silva, J., Lynce, I.: Towards robust CNF encodings of cardinality constraints. In: Bessiere, C. (ed.) Principles and Practice of Constraint Programming. CP 2007. LNCS, vol. 4741, pp. 483–497. Springer, Cham (2007). https://doi.org/10.1007/978-3-540-74970-7_35

14.

Schidler, A., Szeider, S.: A SAT approach to twin-width. In: Phillips, C.A., Speckmann, B. (eds.) Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2022, Alexandria, 9–10 January 2022, pp. 67–77. SIAM (2022). https://doi.org/10.1137/1.9781611977042.6

Titel: A Contraction Tree SAT Encoding for Computing Twin-Width
verfasst von: Yinon Horev
Shiraz Shay
Sarel Cohen
Tobias Friedrich
Davis Issac
Lior Kamma
Aikaterini Niklanovits
Kirill Simonov
Verlag: Springer Nature Singapore
Buch: Advances in Knowledge Discovery and Data Mining
Print ISBN: 978-981-9722-52-5

Electronic ISBN: 978-981-9722-53-2

Copyright-Jahr: 2024
DOI: https://doi.org/10.1007/978-981-97-2253-2_35

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner