License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2020.31
URN: urn:nbn:de:0030-drops-133340
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13334/
Go to the corresponding LIPIcs Volume Portal

Xu, Zijian ; Mao, Dejun ; Suppakitpaisarn, Vorapong

PACE Solver Description: Computing Exact Treedepth via Minimal Separators

pdf-format:
LIPIcs-IPEC-2020-31.pdf (0.4 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{xu_et_al:LIPIcs:2020:13334,
  author =	{Zijian Xu and Dejun Mao and Vorapong Suppakitpaisarn},
  title =	{{PACE Solver Description: Computing Exact Treedepth via Minimal Separators}},
  booktitle =	{15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
  pages =	{31:1--31:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-172-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{180},
  editor =	{Yixin Cao and Marcin Pilipczuk},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13334},
  URN =		{urn:nbn:de:0030-drops-133340},
  doi =		{10.4230/LIPIcs.IPEC.2020.31},
  annote =	{Keywords: Treedepth, Minimal Separators, Experimental Algorithm}
}

Keywords: Treedepth, Minimal Separators, Experimental Algorithm
Collection: 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Issue Date: 2020
Date of publication: 04.12.2020
Supplementary Material: The solver submitted to the competition is available at https://doi.org/10.5281/zenodo.3870624 and the repository is https://github.com/xuzijian629/pace2020.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI