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 wellmotivated 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 nonroot 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 fillin, 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 fillin, 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:122:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771726},
ISSN = {18688969},
year = {2020},
volume = {180},
editor = {Yixin Cao and Marcin Pilipczuk},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13325},
URN = {urn:nbn:de:0030drops133253},
doi = {10.4230/LIPIcs.IPEC.2020.22},
annote = {Keywords: Treewidth, Minimum fillin, Perfect phylogeny, Fractional hypertreewidth, Potential maximal cliques, Edge clique cover}
}
04.12.2020
Keywords: 

Treewidth, Minimum fillin, Perfect phylogeny, Fractional hypertreewidth, Potential maximal cliques, Edge clique cover 
Seminar: 

15th International Symposium on Parameterized and Exact Computation (IPEC 2020)

Issue date: 

2020 
Date of publication: 

04.12.2020 