vix.ing · top · new · best · stats · spec

Finding Optimal Triangulations Parameterized by Edge Clique Cover

2019/12/31 by Tuukka Korhonen
Computer Science · Mathematics · #Algorithm #Bayesian Modeling and Causal Inference #Clique #Combinatorics #Computer science #Constraint Satisfaction and Optimization #Graph #Line graph #Machine Learning and Algorithms #Mathematics #Parameterized complexity #Treewidth #cs.DM #cs.DS

paper · pdf · doi:10.1007/s00453-022-00932-0

28 pages, 3 figures, appeared in IPEC'20, to appear in Algorithmica special issue of IPEC'20

arxiv created 2022/02/02 · openalex publication_date 2022/02/05 · arxiv updated 2022/02/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

Abstract We consider problems that can be formulated as a task of finding an optimal triangulation of a graph w.r.t. some notion of optimality. We present algorithms parameterized by the size of a minimum edge clique cover ( \texttt cc <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>cc</mml:mi></mml:math> ) to such problems. This parameterization occurs naturally in many problems in this setting, e.g., in the perfect phylogeny problem \texttt cc <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>cc</mml:mi></mml:math> is at most the number of taxa, in fractional hypertreewidth \texttt cc <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>cc</mml:mi></mml:math> is at most the number of hyperedges, and in treewidth of Bayesian networks \texttt cc <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>cc</mml:mi></mml:math> is at most the number of non-root nodes. We show that the number of minimal separators of graphs is at most 2^\texttt cc <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mn>2</mml:mn><mml:mi>cc</mml:mi></mml:msup></mml:math> , the number of potential maximal cliques is at most 3^\texttt cc <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mn>3</mml:mn><mml:mi>cc</mml:mi></mml:msup></mml:math> , and these objects can be listed in times O^*(2^\texttt cc) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mi>O</mml:mi><mml:mo>∗</mml:mo></mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:mi>cc</mml:mi></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math> and O^*(3^\texttt cc) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mi>O</mml:mi><mml:mo>∗</mml:mo></mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:msup><mml:mn>3</mml:mn><mml:mi>cc</mml:mi></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math> , respectively, even when no edge clique cover is given as input; the O^*(⋅ ) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mi>O</mml:mi><mml:mo>∗</mml:mo></mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:mo>·</mml:mo><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math> notation omits factors polynomial in the input size. These enumeration algorithms imply O^*(3^\texttt cc) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mi>O</mml:mi><mml:mo>∗</mml:mo></mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:msup><mml:mn>3</mml:mn><mml:mi>cc</mml:mi></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math> time algorithms for problems such as treewidth, weighted minimum fill-in, and feedback vertex set. For generalized and fractional hypertreewidth we give O^*(4m) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mi>O</mml:mi><mml:mo>∗</mml:mo></mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:msup><mml:mn>4</mml:mn><mml:mi>m</mml:mi></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math> time and O^*(3m) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mi>O</mml:mi><mml:mo>∗</mml:mo></mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:msup><mml:mn>3</mml:mn><mml:mi>m</mml:mi></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math> time algorithms, respectively, where m is the number of hyperedges. When an edge clique cover of size \texttt cc' <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>cc</mml:mi><mml:mo>′</mml:mo></mml:msup></mml:math> is given as a part of the input we give O^*(2^\texttt cc') <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mi>O</mml:mi><mml:mo>∗</mml:mo></mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:msup><mml:mi>cc</mml:mi><mml:mo>′</mml:mo></mml:msup></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math> time algorithms for treewidth, minimum fill-in, and chordal sandwich. This implies an O^*(2n) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mi>O</mml:mi><mml:mo>∗</mml:mo></mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:msup><mml:mn>2</mml:mn><mml:mi>n</mml:mi></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math> time algorithm for perfect phylogeny, where n is the number of taxa. We also give polynomial space algorithms with time complexities O^*(9^\texttt cc') <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mi>O</mml:mi><mml:mo>∗</mml:mo></mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:msup><mml:mn>9</mml:mn><mml:msup><mml:mi>cc</mml:mi><mml:mo>′</mml:mo></mml:msup></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math> and O^*(9^\texttt cc+ O(log 2 \texttt cc)) <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msup><mml:mi>O</mml:mi><mml:mo>∗</mml:mo></mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:msup><mml:mn>9</mml:mn><mml:mrow><mml:mi>cc</mml:mi><mml:mo>+</mml:mo><mml:mi>O</mml:mi><mml:mo>(</mml:mo><mml:msup><mml:mo>log</mml:mo><mml:mn>2</mml:mn></mml:msup><mml:mi>cc</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:math> for problems in this framework.

Citations