2026-10-09T09:33:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13334 2024-03-06T09:51:43Z ddc:004 open_access

PACE Solver Description: Computing Exact Treedepth via Minimal Separators Xu, Zijian Mao, Dejun Suppakitpaisarn, Vorapong Treedepth Minimal Separators Experimental Algorithm This is a description of team xuzijian629’s treedepth solver submitted to PACE 2020. As we use a top-down approach, we enumerate all possible minimal separators at each step. The enumeration is sped up by several novel pruning techniques and is based on our conjecture that we can always have an optimal decomposition without using separators with size larger than treewidth. Although we cannot theoretically guarantee that our algorithm based on the unproved conjecture can always give an optimal solution, it can give optimal solutions for all instances in our experiments. The algorithm solved 68 private instances and placed 5th in the competition. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zijian Xu and Dejun Mao and Vorapong Suppakitpaisarn 2020 Is Part Of LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2020.31 urn:nbn:de:0030-drops-133340 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.31 eng https://creativecommons.org/licenses/by/3.0/legalcode