{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:58:20Z","timestamp":1762102700863,"version":"build-2065373602"},"reference-count":89,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2022,1,27]],"date-time":"2022-01-27T00:00:00Z","timestamp":1643241600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Research on the similarity of a graph to being a tree\u2014called the treewidth of the graph\u2014has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017). It is based on dynamic programming and makes use of the fact that the number of positive subinstances is typically substantially smaller than the number of all subinstances. Algorithms producing only such subinstances are called positive-instance driven (PID). The parameter treedepth has a similar story. It was popularized through the graph sparsity project and is theoretically well understood\u2014but the first practical algorithm was discovered only recently by Trimble (IPEC 2020) and is based on the same paradigm. We give an alternative and unifying view on such algorithms from the perspective of the corresponding configuration graphs in certain two-player games. This results in a single algorithm that can compute a wide range of important graph parameters such as treewidth, pathwidth, and treedepth. We complement this algorithm with a novel randomized data structure that accelerates the enumeration of subproblems in positive-instance driven algorithms.<\/jats:p>","DOI":"10.3390\/a15020042","type":"journal-article","created":{"date-parts":[[2022,1,27]],"date-time":"2022-01-27T21:59:55Z","timestamp":1643320795000},"page":"42","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Recent Advances in Positive-Instance Driven Graph Searching"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6475-5512","authenticated-orcid":false,"given":"Max","family":"Bannach","sequence":"first","affiliation":[{"name":"Institute for Theoretical Computer Science, Universit\u00e4t zu L\u00fcbeck, 23562 L\u00fcbeck, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4177-8081","authenticated-orcid":false,"given":"Sebastian","family":"Berndt","sequence":"additional","affiliation":[{"name":"Institute for IT Security, Universit\u00e4t zu L\u00fcbeck, 23562 L\u00fcbeck, Germany"}]}],"member":"1968","published-online":{"date-parts":[[2022,1,27]]},"reference":[{"key":"ref_1","first-page":"147","article-title":"Algorithmic Meta-Theorems","volume":"16","author":"Kreutzer","year":"2009","journal-title":"Electron. Colloq. Comput. Complex. (ECCC)"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. (2015). Parameterized Algorithms, Springer.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"ref_3","unstructured":"Berg, J., J\u00e4rvisalo, M., and Malone, B. (2014, January 22\u201325). Learning optimal bounded treewidth Bayesian networks via maximum satisfiability. Proceedings of the Seventeenth International Conference on Artificial Intelligence and Statistics, Reykjavik, Iceland."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1145\/765568.765570","article-title":"A differential approach to inference in Bayesian networks","volume":"50","author":"Darwiche","year":"2003","journal-title":"J. ACM (JACM)"},{"key":"ref_5","first-page":"2699","article-title":"Learning bounded treewidth Bayesian networks","volume":"9","author":"Elidan","year":"2008","journal-title":"J. Mach. Learn. Res."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1016\/j.disopt.2011.06.001","article-title":"Courcelle\u2019s theorem\u2014A game-theoretic approach","volume":"8","author":"Kneis","year":"2011","journal-title":"Discret. Optim."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Bannach, M., and Berndt, S. (2019). Practical Access to Dynamic Programming on Tree Decompositions. Algorithms, 12.","DOI":"10.3390\/a12080172"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Bjesse, P., Kukula, J.H., Damiano, R.F., Stanion, T., and Zhu, Y. (2003, January 5\u20138). Guiding SAT Diagnosis with Tree Decompositions. Proceedings of the International Conference on Theory and Applications of Satisfiability Testing 2003, Santa Margherita Ligure, Italy.","DOI":"10.1007\/978-3-540-24605-3_24"},{"key":"ref_9","unstructured":"Fichte, J.K., Hecher, M., Woltran, S., and Zisser, M. (2018, January 20\u201322). Weighted Model Counting on the GPU by Exploiting Small Treewidth. Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018), Helsinki, Finland."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Habet, D., Paris, L., and Terrioux, C. (2009, January 2\u20134). A Tree Decomposition Based Approach to Solve Structured SAT Instances. Proceedings of the 2009 21st IEEE International Conference on Tools with Artificial Intelligence, Newark, NJ, USA.","DOI":"10.1109\/ICTAI.2009.76"},{"key":"ref_11","unstructured":"Charwat, G., and Woltran, S. (2016, January 4). Dynamic Programming-based QBF Solving. Proceedings of the QBF 2016, Bordeaux, France."},{"key":"ref_12","unstructured":"Eiben, E., Ganian, R., and Ordyniak, S. (March, January 28). Small Resolution Proofs for QBF using Dependency Treewidth. Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018), Caen, France."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Karakashian, S., Woodward, R.J., and Choueiry, B.Y. (2013, January 14\u201318). Improving the Performance of Consistency Algorithms by Localizing and Bolstering Propagation in a Tree Decomposition. Proceedings of the AAAI Conference on Artificial Intelligence, Bellevue, WA, USA.","DOI":"10.1609\/aaai.v27i1.8594"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1002\/net.10046","article-title":"Solving partial constraint satisfaction problems with tree decomposition","volume":"40","author":"Koster","year":"2002","journal-title":"Networks"},{"key":"ref_15","unstructured":"Eisenbrand, F., Hunkenschr\u00f6der, C., and Klein, K. (2018, January 9\u201313). Faster Algorithms for Integer Programs with Block Structure. Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Ganian, R., Ordyniak, S., and Ramanujan, M.S. (2017, January 4\u20139). Going Beyond Primal Treewidth for (M)ILP. Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, San Francisco, CA, USA.","DOI":"10.1609\/aaai.v31i1.10644"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.artint.2017.12.006","article-title":"The complexity landscape of decompositional parameters for ILP","volume":"257","author":"Ganian","year":"2018","journal-title":"Artif. Intell."},{"key":"ref_18","unstructured":"Kouteck\u00fd, M., Levin, A., and Onn, S. (2018, January 9\u201313). A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs. Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Prague, Czech Republic."},{"key":"ref_19","unstructured":"Szeider, S. (2003, January 5\u20138). On Fixed-Parameter Tractable Parameterizations of SAT. Proceedings of the Theory and Applications of Satisfiability Testing 2003, Santa Margherita Ligure, Italy."},{"key":"ref_20","unstructured":"Bannach, M., Berndt, S., and Ehlers, T. (2017, January 21\u201323). Jdrasil: A Modular Library for Computing Tree Decompositions. Proceedings of the 16th International Symposium on Experimental Algorithms (SEA 2017), London, UK."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1007\/s00778-019-00558-9","article-title":"An analytical study of large SPARQL query logs","volume":"29","author":"Bonifati","year":"2020","journal-title":"VLDB J."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Dudek, J.M., Phan, V.H.N., and Vardi, M.Y. (2020, January 7\u201311). DPMC: Weighted Model Counting by Dynamic Programming on Project-Join Trees. Proceedings of the Principles and Practice of Constraint Programming\u201426th International Conference, CP 2020, Louvain-la-Neuve, Belgium.","DOI":"10.1007\/978-3-030-58475-7_13"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Dudek, J.M., Phan, V.H.N., and Vardi, M.Y. (2021, January 5\u20139). ProCount: Weighted Projected Model Counting with Graded Project-Join Trees. Proceedings of the Theory and Applications of Satisfiability Testing\u2014SAT 2021\u201424th International Conference, Barcelona, Spain.","DOI":"10.1007\/978-3-030-80223-3_11"},{"key":"ref_24","unstructured":"Korhonen, T., and J\u00e4rvisalo, M. (2021, January 25\u201329). Integrating Tree Decompositions into Decision Heuristics of Propositional Model Counters (Short Paper). Proceedings of the 27th International Conference on Principles and Practice of Constraint Programming, CP 2021, (Virtual Conference), Montpellier, France."},{"key":"ref_25","unstructured":"Maniu, S., Senellart, P., and Jog, S. (2019, January 26-28). An Experimental Study of the Treewidth of Real-World Graph Data. Proceedings of the 22nd International Conference on Database Theory, ICDT 2019, Lisbon, Portugal."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Gutin, G.Z., Jones, M., and Wahlstr\u00f6m, M. (2015, January 14\u201316). Structural Parameterizations of the Mixed Chinese Postman Problem. Proceedings of the Algorithms\u2014ESA 2015\u201423rd Annual European Symposium, Patras, Greece.","DOI":"10.1007\/978-3-662-48350-3_56"},{"key":"ref_27","unstructured":"Iwata, Y., Ogasawara, T., and Ohsaka, N. (March, January 28). On the Power of Tree-Depth for Fully Polynomial FPT Algorithms. Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, Caen, France."},{"key":"ref_28","unstructured":"Brand, C., Kouteck\u00fd, M., and Ordyniak, S. (2021, January 2\u20139). Parameterized Algorithms for MILPs with Small Treedepth. Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event."},{"key":"ref_29","unstructured":"Bl\u00e4sius, T., Fischbeck, P., Friedrich, T., and Katzmann, M. (2020, January 10\u201313). Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs. Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, STACS 2020, Montpellier, France."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1007\/s00453-014-9914-4","article-title":"Computing Tree-Depth Faster Than 2n","volume":"73","author":"Fomin","year":"2015","journal-title":"Algorithmica"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Reidl, F., Rossmanith, P., Villaamil, F.S., and Sikdar, S. (2014, January 8\u201311). A Faster Parameterized Algorithm for Treedepth. Proceedings of the Automata, Languages, and Programming\u201441st International Colloquium, ICALP 2014, Copenhagen, Denmark.","DOI":"10.1007\/978-3-662-43948-7_77"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","article-title":"A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth","volume":"25","author":"Bodlaender","year":"1996","journal-title":"SIAM J. Comput."},{"key":"ref_33","unstructured":"R\u00f6hrig, H. (1998). Tree Decomposition: A Feasibility Study. [Master\u2019s Thesis, Max-Planck-Institut f\u00fcr Informatik in Saarbr\u00fccken]."},{"key":"ref_34","unstructured":"Gogate, V., and Dechter, R. (2004, January 7\u201311). A Complete Anytime Algorithm for Treewidth. Proceedings of the UAI\u201904, 20th Conference in Uncertainty in Artificial Intelligence, Banff, AB, Canada."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1.3:1","DOI":"10.1145\/2851494","article-title":"Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth","volume":"21","author":"Coudert","year":"2016","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_36","unstructured":"Trimble, J. (2020, January 16\u201318). An Algorithm for the Exact Treedepth Problem. Proceedings of the 18th International Symposium on Experimental Algorithms, SEA 2020, Catania, Italy."},{"key":"ref_37","first-page":"1","article-title":"Graph Bisection with Pareto Optimization","volume":"23","author":"Hamann","year":"2018","journal-title":"ACM J. Exp. Algorithmics"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/j.ic.2009.03.008","article-title":"Treewidth computations I. Upper bounds","volume":"208","author":"Bodlaender","year":"2010","journal-title":"Inf. Comput."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Tamaki, H. (2019, January 24\u201329). Computing Treewidth via Exact and Heuristic Lists of Minimal Separators. Proceedings of the Analysis of Experimental Algorithms\u2014Special Event, SEA2 2019, Kalamata, Greece.","DOI":"10.1007\/978-3-030-34029-2_15"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Kobayashi, Y., Komuro, K., and Tamaki, H. (July, January 29). Search Space Reduction through Commitments in Pathwidth Computation: An Experimental Study. Proceedings of the Experimental Algorithms\u201413th International Symposium, SEA 2014, Copenhagen, Denmark.","DOI":"10.1007\/978-3-319-07959-2_33"},{"key":"ref_41","unstructured":"(2017). Fernando S\u00e1nchez Villaamil. About Treedepth and Related Notions. [Ph.D. Thesis, RWTH Aachen University]."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Kask, K., Gelfand, A., Otten, L., and Dechter, R. (2011, January 7\u201311). Pushing the Power of Stochastic Greedy Ordering Schemes for Inference in Graphical Models. Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2011, San Francisco, CA, USA.","DOI":"10.1609\/aaai.v25i1.7828"},{"key":"ref_43","unstructured":"Dell, H., Husfeldt, T., Jansen, B., Kaski, P., Komusiewicz, C., and Rosamond, F. (2016, January 24\u201326). The First Parameterized Algorithms and Computational Experiments Challenge. Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), Aarhus, Denmark."},{"key":"ref_44","unstructured":"Dell, H., Komusiewicz, C., Talmon, N., and Weller, M. (2017, January 6\u20138). The PACE 2017 Parameterized Algorithms and Computational Experiments Challenge: The Second Iteration. Proceedings of the 12th International Symposium on Parameterized and Exact Computation (IPEC 2017), Vienna, Austria."},{"key":"ref_45","unstructured":"Kowalik, L., Mucha, M., Nadara, W., Pilipczuk, M., Sorge, M., and Wygocki, P. (2020, January 14\u201318). The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. Proceedings of the 15th International Symposium on Parameterized and Exact Computation, IPEC 2020 (Virtual Conference), Hong Kong, China."},{"key":"ref_46","unstructured":"Tamaki, H. (2017, August 02). Treewidth-Exact. Available online: github.com\/TCS-Meiji\/treewidth-exact."},{"key":"ref_47","unstructured":"Larisch, L., and Salfelder, F. (2017, August 02). p17. Available online: https:\/\/github.com\/freetdi\/p17."},{"key":"ref_48","unstructured":"Trimble, J. (2020, January 14\u201318). PACE Solver Description: Bute-Plus: A Bottom-Up Exact Solver for Treedepth. Proceedings of the 15th International Symposium on Parameterized and Exact Computation, IPEC 2020 (Virtual Conference), Hong Kong, China."},{"key":"ref_49","unstructured":"Bannach, M., Berndt, S., Schuster, M., and Wien\u00f6bst, M. (2020, January 14\u201318). PACE Solver Description: PID\u22c6. Proceedings of the 15th International Symposium on Parameterized and Exact Computation, IPEC 2020 (Virtual Conference), Hong Kong, China."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","article-title":"Complexity of finding embeddings in ak-tree","volume":"8","author":"Arnborg","year":"1987","journal-title":"SIAM J. Algebr. Discret. Methods"},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0304-3975(01)00007-X","article-title":"Listing all potential maximal cliques of a graph","volume":"276","author":"Todinca","year":"2002","journal-title":"Theor. Comput. Sci."},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"1283","DOI":"10.1007\/s10878-018-0353-z","article-title":"Positive-instance driven dynamic programming for treewidth","volume":"37","author":"Tamaki","year":"2019","journal-title":"J. Comb. Optim."},{"key":"ref_53","unstructured":"Althaus, E., Schnurbusch, D., W\u00fcschner, J., and Ziegler, S. (2021, January 7\u20139). On Tamaki\u2019s Algorithm to Compute Treewidths. Proceedings of the 19th International Symposium on Experimental Algorithms, SEA 2021, Nice, France."},{"key":"ref_54","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., and Kratsch, D. (2010). Exact Exponential Algorithms, Springer.","DOI":"10.1007\/978-3-642-16533-7"},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF01917434","article-title":"S-functions for graphs","volume":"8","author":"Halin","year":"1976","journal-title":"J. Geom."},{"key":"ref_56","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","article-title":"Graph minors. I. Excluding a forest","volume":"35","author":"Robertson","year":"1983","journal-title":"JCT J. Comb. Theory"},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","article-title":"Graph Minors. II. Algorithmic Aspects of Tree-Width","volume":"7","author":"Robertson","year":"1986","journal-title":"Algorithms"},{"key":"ref_58","doi-asserted-by":"crossref","unstructured":"Nesetril, J., and de Mendez, P.O. (2012). Sparsity, Springer.","DOI":"10.1007\/978-3-642-27875-4"},{"key":"ref_59","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1006\/jctb.1993.1027","article-title":"Graph Searching and a Min-Max Theorem for Tree-Width","volume":"58","author":"Seymour","year":"1993","journal-title":"JCT J. Comb. Theory"},{"key":"ref_60","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0304-3975(86)90146-5","article-title":"Searching and Pebbling","volume":"47","author":"Kirousis","year":"1986","journal-title":"TCS Theor. Comput. Sci."},{"key":"ref_61","doi-asserted-by":"crossref","first-page":"2089","DOI":"10.1016\/j.dam.2012.03.015","article-title":"LIFO-search: A min-max theorem and a searching game for cycle-rank and tree-depth","volume":"160","author":"Giannopoulou","year":"2012","journal-title":"Discret. Appl. Math."},{"key":"ref_62","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1007\/s00453-007-9041-6","article-title":"Nondeterministic Graph Searching: From Pathwidth to Treewidth","volume":"53","author":"Fomin","year":"2009","journal-title":"Algorithmica"},{"key":"ref_63","doi-asserted-by":"crossref","unstructured":"Tamaki, H. (2020). Experimental Analysis of Treewidth. Treewidth, Kernels, and Algorithms\u2014Essays Dedicated to Hans L. Bodlaender on the Occasion of His 60th Birthday, Springer.","DOI":"10.1007\/978-3-030-42071-0_15"},{"key":"ref_64","unstructured":"Korhonen, T. (2020, January 14\u201318). PACE Solver Description: SMS. Proceedings of the 15th International Symposium on Parameterized and Exact Computation, IPEC 2020 (Virtual Conference), Hong Kong, China."},{"key":"ref_65","unstructured":"Brokkelkamp, R., van Veneti\u00eb, R., de Vries, M.J., and Westerdiep, J. (2020, January 14\u201318). PACE Solver Description: TdULL. Proceedings of the 15th International Symposium on Parameterized and Exact Computation, IPEC 2020 (Virtual Conference), Hong Kong, China."},{"key":"ref_66","doi-asserted-by":"crossref","first-page":"15:1","DOI":"10.1145\/3326159","article-title":"A SAT Approach to Branchwidth","volume":"20","author":"Lodha","year":"2019","journal-title":"ACM Trans. Comput. Log."},{"key":"ref_67","unstructured":"Ramaswamy, V.P., and Szeider, S. (2020, January 7\u201311). MaxSAT-Based Postprocessing for Treedepth. Proceedings of the Principles and Practice of Constraint Programming\u201426th International Conference, CP 2020, Louvain-la-Neuve, Belgium."},{"key":"ref_68","doi-asserted-by":"crossref","unstructured":"Ganian, R., Lodha, N., Ordyniak, S., and Szeider, S. (2019, January 7\u20138). SAT-Encodings for Treecut Width and Treedepth. Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments, ALENEX 2019, San Diego, CA, USA.","DOI":"10.1137\/1.9781611975499.10"},{"key":"ref_69","doi-asserted-by":"crossref","unstructured":"Lodha, N., Ordyniak, S., and Szeider, S. (28\u20131, January 28). SAT-Encodings for Special Treewidth and Pathwidth. Proceedings of the Theory and Applications of Satisfiability Testing\u2014SAT 2017\u201420th International Conference, Melbourne, Australia.","DOI":"10.1007\/978-3-319-66263-3_27"},{"key":"ref_70","doi-asserted-by":"crossref","unstructured":"Samer, M., and Veith, H. (July, January 30). Encoding Treewidth into SAT. Proceedings of the Theory and Applications of Satisfiability Testing\u2014SAT 2009, 12th International Conference, SAT 2009, Swansea, UK.","DOI":"10.1007\/978-3-642-02777-2_6"},{"key":"ref_71","doi-asserted-by":"crossref","unstructured":"Berg, J., and J\u00e4rvisalo, M. (2014, January 10\u201312). SAT-Based Approaches to Treewidth Computation: An Evaluation. Proceedings of the 26th IEEE International Conference on Tools with Artificial Intelligence, Limassol, Cyprus.","DOI":"10.1109\/ICTAI.2014.57"},{"key":"ref_72","doi-asserted-by":"crossref","unstructured":"Bannach, M., and Berndt, S. (2019, January 5\u20137). Positive-Instance Driven Dynamic Programming for Graph Searching. Proceedings of the Algorithms and Data Structures\u201416th International Symposium, WADS 2019, Edmonton, AB, Canada.","DOI":"10.1007\/978-3-030-24766-9_4"},{"key":"ref_73","doi-asserted-by":"crossref","unstructured":"Safari, M. (September, January 29). D-Width: A More Natural Measure for Directed Tree Width. Proceedings of the Mathematical Foundations of Computer Science 2005, Gdansk, Poland.","DOI":"10.1007\/11549345_64"},{"key":"ref_74","unstructured":"Bienstock, D. Graph Searching, Path-Width, Tree-Width and Related Problems (A Survey). Reliability of Computer and Communication Networks, Proceedings of the DIMACS Workshop, New Brunswick, NJ, USA, 2\u20134 December 1989."},{"key":"ref_75","unstructured":"Gruber, H., and Holzer, M. (2008, January 7\u201311). Finite Automata, Digraph Connectivity, and Regular Expression Size. Proceedings of the International Colloquium on Automata, Languages, and Programming, Reykjavik, Iceland."},{"key":"ref_76","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0196-6774(91)90003-H","article-title":"Monotonicity in Graph Searching","volume":"12","author":"Bienstock","year":"1991","journal-title":"J. Algorithms"},{"key":"ref_77","first-page":"224","article-title":"Recontamination Does Not Help to Search a Graph","volume":"40","author":"LaPaugh","year":"1993","journal-title":"ACM"},{"key":"ref_78","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/j.tcs.2008.02.036","article-title":"Monotonicity of non-deterministic graph searching","volume":"399","author":"Mazoit","year":"2008","journal-title":"TCS Theor. Comput. Sci."},{"key":"ref_79","doi-asserted-by":"crossref","unstructured":"Immerman, N. (1999). Descriptive Complexity, Springer.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"ref_80","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1145\/368996.369025","article-title":"Topological sorting of large networks","volume":"5","author":"Kahn","year":"1962","journal-title":"Commun. ACM"},{"key":"ref_81","unstructured":"Evans, W., Hunter, P., and Safari, M. (2007). D-Width and Cops and Robbers, unpublished."},{"key":"ref_82","doi-asserted-by":"crossref","unstructured":"Savnik, I. (2013, January 2\u20136). Index Data Structure for Fast Subset and Superset Queries. Proceedings of the 5th International Cross-Domain Conference on Vailability, Reliability, and Security in Information Systems and HCI, Regensburg, Germany.","DOI":"10.1007\/978-3-642-40511-2_10"},{"key":"ref_83","unstructured":"Flum, J., and Grohe, M. (2006). Parameterized Complexity Theory, Springer."},{"key":"ref_84","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1016\/S1571-0653(05)80078-2","article-title":"Treewidth: Computational Experiments","volume":"8","author":"Koster","year":"2001","journal-title":"Electron. Notes Discret. Math."},{"key":"ref_85","doi-asserted-by":"crossref","unstructured":"Gugelmann, L., Panagiotou, K., and Peter, U. (2012, January 9\u201313). Random Hyperbolic Graphs: Degree Sequence and Clustering\u2014(Extended Abstract). Proceedings of the Automata, Languages, and Programming\u201439th International Colloquium, ICALP 2012, Warwick, UK.","DOI":"10.1007\/978-3-642-31585-5_51"},{"key":"ref_86","unstructured":"Bl\u00e4sius, T., Friedrich, T., and Krohmer, A. (2016, January 22\u201324). Hyperbolic Random Graphs: Separators and Treewidth. Proceedings of the 24th Annual European Symposium on Algorithms, Aarhus, Denmark."},{"key":"ref_87","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1016\/j.cpc.2015.05.028","article-title":"Hyperbolic graph generator","volume":"196","author":"Aldecoa","year":"2015","journal-title":"Comput. Phys. Commun."},{"key":"ref_88","doi-asserted-by":"crossref","first-page":"866","DOI":"10.1016\/j.dam.2010.12.017","article-title":"On the model-checking of monadic second-order formulas with edge set quantifications","volume":"160","author":"Courcelle","year":"2012","journal-title":"Discret. Appl. Math."},{"key":"ref_89","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.dam.2015.01.015","article-title":"Characterizing width two for variants of treewidth","volume":"216","author":"Bodlaender","year":"2017","journal-title":"Discret. Appl. Math."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/42\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:08:50Z","timestamp":1760134130000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/2\/42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,27]]},"references-count":89,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2022,2]]}},"alternative-id":["a15020042"],"URL":"https:\/\/doi.org\/10.3390\/a15020042","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,1,27]]}}}