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.22
URN: urn:nbn:de:0030-drops-133253
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13325/
Korhonen, Tuukka
Finding Optimal Triangulations Parameterized by Edge Clique Cover
Abstract
Many graph problems can be formulated as a task of finding an optimal triangulation of a given graph with respect to some notion of optimality. In this paper we give algorithms to such problems parameterized by the size of a minimum edge clique cover (cc) of the graph. The parameter cc is both natural and well-motivated in many problems on this setting. For example, in the perfect phylogeny problem cc is at most the number of taxa, in fractional hypertreewidth cc is at most the number of hyperedges, and in treewidth of Bayesian networks cc is at most the number of non-root nodes of the Bayesian network.
Our results are based on the framework of potential maximal cliques. We show that the number of minimal separators of graphs is at most 2^cc and the number of potential maximal cliques is at most 3^cc. Furthermore, these objects can be listed in times O^*(2^cc) and O^*(3^cc), respectively, even when no edge clique cover is given as input; the O^*(⋅) notation omits factors polynomial in the input size. Using these enumeration algorithms we obtain O^*(3^cc) time algorithms for problems in the potential maximal clique framework, including for example treewidth, minimum fill-in, and feedback vertex set. We also obtain an O^*(3^m) time algorithm for fractional hypertreewidth, where m is the number of hyperedges. In the case when an edge clique cover of size cc' is given as an input we further improve the time complexity to O^*(2^cc') for treewidth, minimum fill-in, and chordal sandwich. This implies an O^*(2^n) time algorithm for perfect phylogeny, where n is the number of taxa. We also give polynomial space algorithms with time complexities O^*(9^cc') and O^*(9^(cc + O(log^2 cc))) for problems in this framework.
BibTeX - Entry
@InProceedings{korhonen:LIPIcs:2020:13325,
author = {Tuukka Korhonen},
title = {{Finding Optimal Triangulations Parameterized by Edge Clique Cover}},
booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
pages = {22:1--22:18},
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/13325},
URN = {urn:nbn:de:0030-drops-133253},
doi = {10.4230/LIPIcs.IPEC.2020.22},
annote = {Keywords: Treewidth, Minimum fill-in, Perfect phylogeny, Fractional hypertreewidth, Potential maximal cliques, Edge clique cover}
}
|
Keywords: |
|
Treewidth, Minimum fill-in, Perfect phylogeny, Fractional hypertreewidth, Potential maximal cliques, Edge clique cover |
|
Collection: |
|
15th International Symposium on Parameterized and Exact Computation (IPEC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.12.2020 |
