References

All works cited in the paper. Each section page also lists the works it cites at its end.

Abu-Khzam, Faisal N., Henning Fernau, Benjamin Gras, Mathieu Liedloff, and Kevin Mann. 2022. “Enumerating Minimal Connected Dominating Sets.” In 30th Annual European Symposium on Algorithms, ESA 2022, 244:1:1–15. LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2022.1.

———. 2025. “Enumerating Minimal Connected Dominating Sets.” SIAM Journal on Discrete Mathematics 39 (2): 946–72. https://doi.org/10.1137/23M1611233.

Abu-Khzam, Faisal N., Amer E. Mouawad, and Mathieu Liedloff. 2010. “An Exact Algorithm for Connected Red-Blue Dominating Set.” In Algorithms and Complexity, 7th International Conference, CIAC 2010, 6078:25–36. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/978-3-642-13073-1_4.

———. 2011. “An Exact Algorithm for Connected Red-Blue Dominating Set.” Journal of Discrete Algorithms 9 (3): 252–62. https://doi.org/10.1016/j.jda.2011.03.006.

Alon, Noga, Fedor V. Fomin, Gregory Z. Gutin, Michael Krivelevich, and Saket Saurabh. 2009. “Spanning Directed Trees with Many Leaves.” SIAM Journal on Discrete Mathematics 23 (1): 466–76. https://doi.org/10.1137/070710494.

Alt, Helmut, Leonidas J. Guibas, Kurt Mehlhorn, Richard M. Karp, and Avi Wigderson. 1996. “A Method for Obtaining Randomized Algorithms with Small Tail Probabilities.” Algorithmica 16 (4/5): 543–47. https://doi.org/10.1007/BF01940879.

Andreev, Nikita, Ivan Bliznets, Madhumita Kundu, Saket Saurabh, Vikash Tripathi, and Shaily Verma. 2024. “Parameterized Complexity of Paired Domination.” In Combinatorial Algorithms, 35th International Workshop, IWOCA 2024, 14764:523–36. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/978-3-031-63021-7_40.

Betzler, Nadja, René van Bevern, Michael R. Fellows, Christian Komusiewicz, and Rolf Niedermeier. 2011. “Parameterized Algorithmics for Finding Connected Motifs in Biological Networks.” IEEE/ACM Transactions on Computational Biology and Bioinformatics 8 (5): 1296–1308. https://doi.org/10.1109/TCBB.2011.19.

Binkele-Raible, Daniel, and Henning Fernau. 2012. “An Exact Exponential-Time Algorithm for the Directed Maximum Leaf Spanning Tree Problem.” Journal of Discrete Algorithms 15: 43–55. https://doi.org/10.1016/j.jda.2012.03.006.

———. 2014. “A Parameterized Measure-and-Conquer Analysis for Finding a \(k\)-Leaf Spanning Tree in an Undirected Graph.” Discrete Mathematics & Theoretical Computer Science 16 (1): 179–200. https://doi.org/10.46298/dmtcs.1256.

Binkele-Raible, Daniel, Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger. 2012. “Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves.” ACM Transactions on Algorithms 8 (4): 38:1–19. https://doi.org/10.1145/2344422.2344428.

Björklund, Andreas, Petteri Kaski, and Łukasz Kowalik. 2016. “Constrained Multilinear Detection and Generalized Graph Motifs.” Algorithmica 74 (2): 947–67. https://doi.org/10.1007/s00453-015-9981-1.

Buchanan, Austin, Yiming Wang, and Sergiy Butenko. 2018. “Algorithms for Node-Weighted Steiner Tree and Maximum-Weight Connected Subgraph.” Networks 72 (2): 238–48. https://doi.org/10.1002/net.21825.

Calabro, Chris, Russell Impagliazzo, and Ramamohan Paturi. 2006. “A Duality Between Clause Width and Clause Density for SAT.” In 21st Annual IEEE Conference on Computational Complexity, CCC 2006, 252–60. https://doi.org/10.1109/CCC.2006.6.

Caro, Yair, Douglas B. West, and Raphael Yuster. 2000. “Connected Domination and Spanning Trees with Many Leaves.” SIAM Journal on Discrete Mathematics 13 (2): 202–11. https://doi.org/10.1137/S0895480199353780.

Claude (Anthropic). 2026. “A \(2^{o(n)}\) Time Algorithm for 3-SAT.” Paper dated 26 October 2026, with a Lean 4 formalization. https://github.com/anthropics/formal-math/tree/16a5ce41304fcdaea4e0be7c132e1c361dc26da5/eth.

Csikvári, Péter, and Zhicong Lin. 2014. “Graph Homomorphisms Between Trees.” The Electronic Journal of Combinatorics 21 (4): P4.9. https://doi.org/10.37236/4096.

Cygan, Marek. 2012. “Deterministic Parameterized Connected Vertex Cover.” In Algorithm Theory – SWAT 2012, 13th Scandinavian Symposium and Workshops, 7357:95–106. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/978-3-642-31155-0_9.

Cygan, Marek, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. 2016. “On Problems as Hard as CNF-SAT.” ACM Transactions on Algorithms 12 (3): 41:1–24. https://doi.org/10.1145/2925416.

Cygan, Marek, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer. https://doi.org/10.1007/978-3-319-21275-3.

Cygan, Marek, Jesper Nederlof, Marcin Pilipczuk, Michał Pilipczuk, Johan M. M. van Rooij, and Jakub Onufry Wojtaszczyk. 2011a. “Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time.” In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, 150–59. IEEE Computer Society. https://doi.org/10.1109/FOCS.2011.23.

———. 2011b. “Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time.” CoRR abs/1103.0534. https://arxiv.org/abs/1103.0534.

———. 2022. “Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time.” ACM Transactions on Algorithms 18 (2): 17:1–31. https://doi.org/10.1145/3506707.

Daligault, Jean, Gregory Gutin, Eun Jung Kim, and Anders Yeo. 2010. “FPT Algorithms and Kernels for the Directed \(k\)-Leaf Problem.” Journal of Computer and System Sciences 76 (2): 144–52. https://doi.org/10.1016/j.jcss.2009.06.005.

Dunbar, Jean E., Jerrold W. Grossman, Johannes H. Hattingh, Stephen T. Hedetniemi, and Alice A. McRae. 1997. “On Weakly Connected Domination in Graphs.” Discrete Mathematics 167–168: 261–69. https://doi.org/10.1016/S0012-365X(96)00233-6.

Esmer, Baris Can, and Ariel Kulik. 2025. “Sampling with a Black Box: Faster Parameterized Approximation Algorithms for Vertex Deletion Problems.” In 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, 334:39:1–20. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2025.39.

Esmer, Baris Can, Ariel Kulik, Dániel Marx, Daniel Neuen, and Roohani Sharma. 2022. “Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search.” In 30th Annual European Symposium on Algorithms, ESA 2022, 244:50:1–19. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2022.50.

———. 2023. “Approximate Monotone Local Search for Weighted Problems.” In 18th International Symposium on Parameterized and Exact Computation, IPEC 2023, 285:17:1–23. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2023.17.

———. 2024. “Optimally Repurposing Existing Algorithms to Obtain Exponential-Time Approximations.” In Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, 314–45. SIAM. https://doi.org/10.1137/1.9781611977912.13.

———. 2026. “Approximate Monotone Local Search for Weighted Problems.” Algorithmica 88 (5): 59. https://doi.org/10.1007/s00453-026-01402-7.

Feldmann, Andreas Emil, and Dániel Marx. 2023. “The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems.” ACM Transactions on Computation Theory 15 (3-4): 4:1–28. https://doi.org/10.1145/3580376.

Fellows, Michael R., Guillaume Fertin, Danny Hermelin, and Stéphane Vialette. 2011. “Upper and Lower Bounds for Finding Connected Motifs in Vertex-Colored Graphs.” Journal of Computer and System Sciences 77 (4): 799–811. https://doi.org/10.1016/j.jcss.2010.07.003.

Fernau, Henning, Joachim Kneis, Dieter Kratsch, Alexander Langer, Mathieu Liedloff, Daniel Raible, and Peter Rossmanith. 2011. “An Exact Algorithm for the Maximum Leaf Spanning Tree Problem.” Theoretical Computer Science 412 (45): 6290–6302. https://doi.org/10.1016/j.tcs.2011.07.011.

Fertin, Guillaume, and Christian Komusiewicz. 2020. “Graph Motif Problems Parameterized by Dual.” Journal of Graph Algorithms and Applications 24 (3): 371–96. https://doi.org/10.7155/jgaa.00538.

Fomin, Fedor V., Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, and Saket Saurabh. 2010. “Iterative Compression and Exact Algorithms.” Theoretical Computer Science 411 (7-9): 1045–53. https://doi.org/10.1016/j.tcs.2009.11.012.

Fomin, Fedor V., Serge Gaspers, Daniel Lokshtanov, and Saket Saurabh. 2019. “Exact Algorithms via Monotone Local Search.” Journal of the ACM 66 (2): 8:1–23. https://doi.org/10.1145/3284176.

Fomin, Fedor V., Serge Gaspers, Artem V. Pyatkin, and Igor Razgon. 2008. “On the Minimum Feedback Vertex Set Problem: Exact and Enumeration Algorithms.” Algorithmica 52 (2): 293–307. https://doi.org/10.1007/s00453-007-9152-0.

Fomin, Fedor V., Fabrizio Grandoni, and Dieter Kratsch. 2008. “Solving Connected Dominating Set Faster Than \(2^n\).” Algorithmica 52 (2): 153–66. https://doi.org/10.1007/s00453-007-9145-z.

———. 2009. “A Measure & Conquer Approach for the Analysis of Exact Algorithms.” Journal of the ACM 56 (5): 25:1–32. https://doi.org/10.1145/1552285.1552286.

Fomin, Fedor V., Fabrizio Grandoni, Dieter Kratsch, Daniel Lokshtanov, and Saket Saurabh. 2013. “Computing Optimal Steiner Trees in Polynomial Space.” Algorithmica 65 (3): 584–604. https://doi.org/10.1007/s00453-012-9612-z.

Fomin, Fedor V., Fabrizio Grandoni, Artem V. Pyatkin, and Alexey A. Stepanov. 2008. “Combinatorial Bounds via Measure and Conquer: Bounding Minimal Dominating Sets and Applications.” ACM Transactions on Algorithms 5 (1): 9:1–17. https://doi.org/10.1145/1435375.1435384.

Fomin, Fedor V., Petteri Kaski, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. 2019. “Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree.” SIAM Journal on Discrete Mathematics 33 (1): 327–45. https://doi.org/10.1137/17M1140030.

Fomin, Fedor V., and Dieter Kratsch. 2010. Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer. https://doi.org/10.1007/978-3-642-16533-7.

Fomin, Fedor V., Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. 2016. “Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms.” Journal of the ACM 63 (4): 29:1–60. https://doi.org/10.1145/2886094.

Galvin, David, Phillip Marmorino, Emily McMillon, JD Nir, and Amanda Redlich. 2025. “Hoffman–London Graphs: When Paths Minimize \(H\)-Colorings Among Trees.” https://arxiv.org/abs/2512.23828.

Galvin, David, Emily McMillon, JD Nir, and Amanda Redlich. 2025. “Long Paths Need Not Minimize \(H\)-Colorings Among Trees.” https://arxiv.org/abs/2510.18770.

Gaspers, Serge. 2026. “Monotone Local Search with Sample-Dependent Running Times: Companion Site with Ancillary Programs, Certificates and Lean 4 Formalization.” Software and data, version v1.1. https://doi.org/10.5281/zenodo.23851002.

Gaspers, Serge, and Edward J. Lee. 2017. “Exact Algorithms via Multivariate Subroutines.” In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, 80:69:1–13. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2017.69.

Golovach, Petr A., Pinar Heggernes, and Dieter Kratsch. 2016. “Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs.” In Combinatorial Algorithms, 26th International Workshop, IWOCA 2015, 9538:235–47. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/978-3-319-29516-9_20.

———. 2018. “Enumeration and Maximum Number of Minimal Connected Vertex Covers in Graphs.” European Journal of Combinatorics 68: 132–47. https://doi.org/10.1016/j.ejc.2017.07.015.

Guglielmi, Nicola, and Vladimir Protasov. 2013. “Exact Computation of Joint Spectral Characteristics of Linear Operators.” Foundations of Computational Mathematics 13 (1): 37–97. https://doi.org/10.1007/s10208-012-9121-0.

Guillemot, Sylvain, and Florian Sikora. 2013. “Finding and Counting Vertex-Colored Subtrees.” Algorithmica 65 (4): 828–44. https://doi.org/10.1007/s00453-011-9600-8.

Impagliazzo, Russell, Ramamohan Paturi, and Francis Zane. 2001. “Which Problems Have Strongly Exponential Complexity?” Journal of Computer and System Sciences 63 (4): 512–30. https://doi.org/10.1006/jcss.2001.1774.

Johansson, Fredrik. 2017. “Arb: Efficient Arbitrary-Precision Midpoint-Radius Interval Arithmetic.” IEEE Transactions on Computers 66 (8): 1281–92. https://doi.org/10.1109/TC.2017.2690633.

Johnson, David S. 1974. “Approximation Algorithms for Combinatorial Problems.” Journal of Computer and System Sciences 9 (3): 256–78. https://doi.org/10.1016/S0022-0000(74)80044-9.

Jones, Mark, Daniel Lokshtanov, M. S. Ramanujan, Saket Saurabh, and Ondřej Suchý. 2017. “Parameterized Complexity of Directed Steiner Tree on Sparse Graphs.” SIAM Journal on Discrete Mathematics 31 (2): 1294–1327. https://doi.org/10.1137/15M103618X.

Kabanets, Valentine, and Russell Impagliazzo. 2004. “Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds.” Computational Complexity 13 (1-2): 1–46. https://doi.org/10.1007/s00037-004-0182-6.

Kneis, Joachim, Alexander Langer, and Peter Rossmanith. 2011. “A New Algorithm for Finding Trees with Many Leaves.” Algorithmica 61 (4): 882–97. https://doi.org/10.1007/s00453-010-9454-5.

Koutis, Ioannis. 2012. “Constrained Multilinear Detection for Faster Functional Motif Discovery.” Information Processing Letters 112 (22): 889–92. https://doi.org/10.1016/j.ipl.2012.08.008.

Koutis, Ioannis, and Ryan Williams. 2009. “Limits and Applications of Group Algebras for Parameterized Problems.” In Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Part I, 5555:653–64. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/978-3-642-02927-1_54.

———. 2016. “Limits and Applications of Group Algebras for Parameterized Problems.” ACM Transactions on Algorithms 12 (3): 31:1–18. https://doi.org/10.1145/2885499.

Lacroix, Vincent, Cristina G. Fernandes, and Marie-France Sagot. 2006. “Motif Search in Graphs: Application to Metabolic Networks.” IEEE/ACM Transactions on Computational Biology and Bioinformatics 3 (4): 360–68. https://doi.org/10.1109/TCBB.2006.55.

Lee, Edward J. 2021. “Exponential Time Algorithms via Separators and Random Subsets.” PhD thesis, University of New South Wales, Sydney, Australia. https://doi.org/10.26190/unsworks/22740.

Lokshtanov, Daniel, and Jesper Nederlof. 2010. “Saving Space by Algebraization.” In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, 321–30. ACM. https://doi.org/10.1145/1806689.1806735.

Lokshtanov, Daniel, Michał Pilipczuk, and Saket Saurabh. 2018. “Below All Subsets for Minimal Connected Dominating Set.” SIAM Journal on Discrete Mathematics 32 (3): 2332–45. https://doi.org/10.1137/17M1138753.

Lovász, László. 1975. “On the Ratio of Optimal Integral and Fractional Covers.” Discrete Mathematics 13 (4): 383–90. https://doi.org/10.1016/0012-365X(75)90058-8.

Lu, Edward. 2020. “The \(k\)-Leaf Spanning Tree Problem.” Honours thesis, UNSW Sydney.

Luby, Michael, Alistair Sinclair, and David Zuckerman. 1993. “Optimal Speedup of Las Vegas Algorithms.” Information Processing Letters 47 (4): 173–80. https://doi.org/10.1016/0020-0190(93)90029-9.

Misra, Neeldhara, Geevarghese Philip, Venkatesh Raman, Saket Saurabh, and Somnath Sikdar. 2012. “FPT Algorithms for Connected Feedback Vertex Set.” Journal of Combinatorial Optimization 24 (2): 131–46. https://doi.org/10.1007/s10878-011-9394-2.

Naor, Moni, Leonard J. Schulman, and Aravind Srinivasan. 1995. “Splitters and Near-Optimal Derandomization.” In 36th Annual Symposium on Foundations of Computer Science, FOCS 1995, 182–91. IEEE Computer Society. https://doi.org/10.1109/SFCS.1995.492475.

Nederlof, Jesper. 2009. “Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems.” In Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Part I, 5555:713–25. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/978-3-642-02927-1_59.

———. 2013. “Fast Polynomial-Space Algorithms Using Inclusion-Exclusion.” Algorithmica 65 (4): 868–84. https://doi.org/10.1007/s00453-012-9630-x.

OpenAI. 2026. “The Exponential Time Hypothesis Is False.” OpenAI Math Release preprint, revised 25 October 2026. https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf.

Paturi, Ramamohan, Pavel Pudlák, Michael E. Saks, and Francis Zane. 2005. “An Improved Exponential-Time Algorithm for \(k\)-SAT.” Journal of the ACM 52 (3): 337–64. https://doi.org/10.1145/1066100.1066101.

PVC (Research Infrastructure), UNSW Sydney. 2010. “Katana.” UNSW, Sydney. https://doi.org/10.26190/669X-A286.

Raible, Daniel, and Henning Fernau. 2009. “A Faster Exact Algorithm for the Directed Maximum Leaf Spanning Tree Problem.” CoRR abs/0911.1900. https://arxiv.org/abs/0911.1900.

Rosenfeld, Matthieu. 2021. “The Growth Rate over Trees of Any Family of Sets Defined by a Monadic Second Order Formula Is Semi-Computable.” In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, 776–95. SIAM. https://doi.org/10.1137/1.9781611976465.49.

Rote, Günter. 2019. “The Maximum Number of Minimal Dominating Sets in a Tree.” In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, 1201–14. SIAM. https://doi.org/10.1137/1.9781611975482.73.

Scaman, Kevin. 2023. “Black-Box Acceleration of Las Vegas Algorithms and Algorithmic Reverse Jensen’s Inequalities.” CoRR abs/2304.11017. https://doi.org/10.48550/arXiv.2304.11017.

Schwartz, Jacob T. 1980. “Fast Probabilistic Algorithms for Verification of Polynomial Identities.” Journal of the ACM 27 (4): 701–17. https://doi.org/10.1145/322217.322225.

Sidorenko, Alexander. 1994. “A Partially Ordered Set of Functionals Corresponding to Graphs.” Discrete Mathematics 131 (1–3): 263–77. https://doi.org/10.1016/0012-365X(94)90388-3.

Tutte, W. T. 1947. “The Factorization of Linear Graphs.” Journal of the London Mathematical Society s1-22 (2): 107–11. https://doi.org/10.1112/jlms/s1-22.2.107.

Zamir, Or. 2023. “The Wrong Direction of Jensen’s Inequality Is Algorithmically Right.” In 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, 261:107:1–10. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.107.

Zehavi, Meirav. 2015. “The \(k\)-Leaf Spanning Tree Problem Admits a Klam Value of 39.” https://arxiv.org/abs/1502.07725.

———. 2018. “The \(k\)-Leaf Spanning Tree Problem Admits a Klam Value of 39.” European Journal of Combinatorics 68: 175–203. https://doi.org/10.1016/j.ejc.2017.07.018.

Zippel, Richard. 1979. “Probabilistic Algorithms for Sparse Polynomials.” In Symbolic and Algebraic Computation, EUROSAM ’79, 72:216–26. Lecture Notes in Computer Science. Springer. https://doi.org/10.1007/3-540-09519-5_73.