More Web Proxy on the site http://driver.im/

research-article

Solving Graph Problems via Potential Maximal Cliques: An Experimental Evaluation of the Bouchitté--Todinca Algorithm

Authors:

Tuukka Korhonen,

Matti JärvisaloAuthors Info & Claims

Journal of Experimental Algorithmics (JEA), Volume 24

Article No.: 1.9, Pages 1 - 19

https://doi.org/10.1145/3301297

Published: 18 February 2019 Publication History

Abstract

The BT algorithm of Bouchitté and Todinca based on enumerating potential maximal cliques, originally proposed for the treewidth and minimum fill-in problems, yields improved exact exponential-time algorithms for various graph optimization problems related to optimal triangulations. While the BT algorithm has received significant attention in terms of theoretical analysis, less attention has been paid on engineering efficient implementations of the algorithm for different problems and thereby on empirical studies on its effectiveness in practice. In this work, we provide an experimental evaluation of an implementation of the BT algorithm, based on our second-place winning entry in the 2nd Parameterized Algorithms and Computational Experiments Challenge (PACE 2017), extended to several related graph problems: treewidth, minimum fill-in, generalized and fractional hypertreewidth, and the total table size problem. Instead of focusing on problem-specific optimization of BT for a particular problem, our focus in this work is on studying the applicability of BT more generally to a range of problems. Based on the results, we conclude that an efficient implementation of the BT algorithm yields an empirically competitive approach to each of the considered problems when compared to available implementations of alternative problem-specific algorithmic approaches.

References

[1]

Mario Alviano, Carmine Dodaro, and Francesco Ricca. 2015. A MaxSAT algorithm using cardinality constraints of bounded size. In Proc. AAAI. AAAI Press, 2677--2683.

Digital Library

[2]

Carlos Ansótegui, Fahiem Bacchus, Matti Järvisalo, and Ruben Martins. 2017. MaxSAT Evaluation 2017. Retrieved from http://mse17.cs.helsinki.fi/.

[3]

Jeremias Berg and Matti Järvisalo. 2014. SAT-based approaches to treewidth computation: An evaluation. In Proc. ICTAI. IEEE Computer Society, 328--335.

Digital Library

[4]

David Bergman, Carlos H. Cardonha, André Augusto Ciré, and Arvind U. Raghunathan. 2016. On the minimum chordal completion polytope. CoRR abs/1612.01966. Retrieved from http://arxiv.org/abs/1612.01966.

[5]

David Bergman and Arvind U. Raghunathan. 2015. A Benders approach to the minimum chordal completion problem. In Proc. CPAIOR (Lecture Notes in Computer Science), Vol. 9075. Springer, 47--64.

[6]

Anne Berry, Jean R. S. Blair, Pinar Heggernes, and Barry W. Peyton. 2004. Maximum cardinality search for computing minimal triangulations of graphs. Algorithmica 39, 4 (2004), 287--298.

Digital Library

[7]

Anne Berry, Jean-Paul Bordat, and Olivier Cogis. 1999. Generating all the minimal separators of a graph. In Proc. WG (Lecture Notes in Computer Science), Vol. 1665. Springer, 167--172.

Digital Library

[8]

Umberto Bertele and Francesco Brioschi. 1972. Nonserial Dynamic Programming. Academic Press, Inc., Orlando, FL.

Digital Library

[9]

Hans L Bodlaender. 1998. A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1 (1998), 1--45.

Digital Library

[10]

Hans L. Bodlaender. 2005. Discovering treewidth. In Proc. SOFSEM (Lecture Notes in Computer Science), Vol. 3381. Springer, 1--16.

Digital Library

[11]

Hans L. Bodlaender and Fedor V. Fomin. 2005. Tree decompositions with small cost. Discrete Appl. Math. 145, 2 (2005), 143--154.

Digital Library

[12]

Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, and Dimitrios M. Thilikos. 2012. On exact algorithms for treewidth. ACM Trans. Algorithms 9, 1, Article 12 (2012).

Digital Library

[13]

Hans L Bodlaender, John R Gilbert, Hjálmtyr Hafsteinsson, and Ton Kloks. 1995. Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Alg. 18, 2 (1995), 238--255.

Digital Library

[14]

Hans L. Bodlaender, Pinar Heggernes, and Yngve Villanger. 2011. Faster parameterized algorithms for minimum fill-in. Algorithmica 61, 4 (2011), 817--838.

Digital Library

[15]

Hans L. Bodlaender and Arie M. C. A. Koster. 2006. Safe separators for treewidth. Discrete Math. 306, 3 (2006), 337--350.

Digital Library

[16]

Vincent Bouchitté and Ioan Todinca. 2001. Treewidth and minimum fill-in: Grouping the minimal separators. SIAM J. Comput. 31, 1 (2001), 212--232.

Digital Library

[17]

Vincent Bouchitté and Ioan Todinca. 2002. Listing all potential maximal cliques of a graph. Theor. Comput. Sci. 276, 1 (2002), 17--32.

Digital Library

[18]

Gregory F. Cooper. 1990. The computational complexity of probabilistic inference using Bayesian belief networks. Artif. Intell. 42, 2--3 (1990), 393--405.

Digital Library

[19]

Jessica Davies and Fahiem Bacchus. 2013. Exploiting the power of MIP solvers in MaxSAT. In Proc. SAT (Lecture Notes in Computer Science), Vol. 7962. Springer, 166--181.

Digital Library

[20]

Rina Dechter. 1999. Bucket elimination: A unifying framework for reasoning. Artif. Intell. 113, 1--2 (1999), 41--85.

Digital Library

[21]

Holger Dell, Thore Husfeldt, Bart M. P. Jansen, Petteri Kaski, Christian Komusiewicz, and Frances A. Rosamond. 2016. The first parameterized algorithms and computational experiments challenge. In Proc. IPEC (LIPIcs), Vol. 63. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 30:1--30:9.

[22]

Holger Dell, Christian Komusiewicz, Nimrod Talmon, and Mathias Weller. 2018. The PACE 2017 parameterized algorithms and computational experiments challenge: The second iteration. In Proc. IPEC 2017 (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 30:1--30:12.

[23]

Fedor V. Fomin, Dieter Kratsch, Ioan Todinca, and Yngve Villanger. 2008. Exact algorithms for treewidth and minimum fill-in. SIAM J. Comput. 38, 3 (2008), 1058--1079.

Digital Library

[24]

Fedor V. Fomin, Ioan Todinca, and Yngve Villanger. 2015. Large induced subgraphs via triangulations and CMSO. SIAM J. Comput. 44, 1 (2015), 54--87.

Digital Library

[25]

Fedor V. Fomin and Yngve Villanger. 2008. Treewidth computation and extremal combinatorics. In Proc. ICALP (Lecture Notes in Computer Science), Vol. 5125. Springer, 210--221.

Digital Library

[26]

Eugene C. Freuder. 1990. Complexity of K-tree structured constraint satisfaction problems. In Proc. AAAI. AAAI Press, 4--9.

Digital Library

[27]

Masanobu Furuse and Koichi Yamazaki. 2014. A revisit of the scheme for computing treewidth and minimum fill-in. Theor. Comput. Sci. 531 (2014), 66--76.

[28]

Tobias Ganzow, Georg Gottlob, Nysret Musliu, and Marko Samer. 2005. A CSP Hypergraph Library. Technical Report DBAI-TR-2005-50. Vienna University of Technology Institute of Information Systems (DBAI).

[29]

Fǎnicǎ Gavril. 1974. The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory, Series B 16, 1 (1974), 47--56.

[30]

Vibhav Gogate and Rina Dechter. 2004. A complete anytime algorithm for treewidth. In Proc. UAI. AUAI Press, 201--208.

Digital Library

[31]

Georg Gottlob, Nicola Leone, and Francesco Scarcello. 2002. Hypertree decompositions and tractable queries. J. Comput. System Sci. 64, 3 (2002), 579--627.

Digital Library

[32]

Georg Gottlob and Marko Samer. 2009. A backtracking-based algorithm for hypertree decomposition. ACM J. Exp. Algorithmics 13, Article 1 (2009).

Digital Library

[33]

Martin Grohe and Dániel Marx. 2014. Constraint solving via fractional edge covers. ACM Trans. Algorithms 11, 1, Article 4 (2014).

Digital Library

[34]

Rob Gysel. 2014. Minimal triangulation algorithms for perfect phylogeny problems. In Proc. LATA (Lecture Notes in Computer Science), Vol. 8370. Springer, 421--432.

Digital Library

[35]

Rob Gysel, Kristian Stevens, and Dan Gusfield. 2012. Reducing problems in unrooted tree compatibility to restricted triangulations of intersection graphs. In Proc. WABI (Lecture Notes in Computer Science), Vol. 7534. Springer, 93--105.

Digital Library

[36]

IBM ILOG. 2017. CPLEX Optimizer 12.7.0. Retrieved from https://www.ibm.com/analytics/data-science/prescriptive-analytics/cplex-optimizer.

[37]

Finn V. Jensen and Frank Jensen. 1994. Optimal junction trees. In Proc. UAI. Morgan Kaufmann Publishers Inc., 360--366.

Digital Library

[38]

Sampath K. Kannan and Tandy J. Warnow. 1994. Inferring evolutionary history from DNA sequences. SIAM J. Comput. 23, 4 (1994), 713--737.

Digital Library

[39]

Uffe Kjaerulff. 1990. Triangulation of Graphs — Algorithms Giving Small Total State Space. Research Report R-90-09. Department of Mathematics and Computer Science, Aalborg University, Denmark.

[40]

Steffen L. Lauritzen and David J. Spiegelhalter. 1988. Local computations with probabilities on graphical structures and their application to expert systems. J. R. Stat. Soc. Series B (Methodological) 50, 2 (1988), 157--194.

[41]

Chao Li and Maomi Ueno. 2017. An extended depth-first search algorithm for optimal triangulation of Bayesian networks. Int. J. Approximate Reasoning 80 (2017), 294--312.

Digital Library

[42]

A Makhorin. 2001. GLPK-the GNU Linear Programming Toolkit. Retrieved from https://www.gnu.org/software/glpk/.

[43]

Ruben Martins, Vasco M. Manquinho, and Inês Lynce. 2014. Open-WBO: A modular MaxSAT solver. In Proc. SAT (Lecture Notes in Computer Science), Vol. 8561. Springer, 438--445.

[44]

Dániel Marx. 2010. Approximating fractional hypertree width. ACM Trans. Algorithms 6, 2, Article 29 (2010), 17 pages.

Digital Library

[45]

Lukas Moll, Siamak Tazari, and Marc Thurley. 2012. Computing hypergraph width measures exactly. Inform. Process. Lett. 112, 6 (2012), 238--242.

Digital Library

[46]

Assaf Natanzon, Ron Shamir, and Roded Sharan. 2000. A polynomial approximation algorithm for the minimum fill-in problem. SIAM J. Comput. 30, 4 (2000), 1067--1079.

Digital Library

[47]

Thorsten J. Ottosen and Jirí Vomlel. 2012. All roads lead to Rome—New search methods for the optimal triangulation problem. Int. J. Approximate Reasoning 53, 9 (2012), 1350--1366.

Digital Library

[48]

Neil Robertson and Paul D. Seymour. 1986. Graph minors. II. algorithmic aspects of tree-width. J. Algorithms 7, 3 (1986), 309--322.

[49]

Donald J. Rose. 1970. Triangulated graphs and the elimination process. J. Math. Anal. Appl. 32, 3 (1970), 597--609.

[50]

Donald J. Rose, R. Endre Tarjan, and George S. Lueker. 1976. Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. 5, 2 (1976), 266--283.

Digital Library

[51]

Werner Schafhauser. 2006. New heuristic methods for tree decompositions and generalized hypertree decompositions. Master’s thesis. Vienna University of Technology.

[52]

Hisao Tamaki. 2017. Positive-instance driven dynamic programming for treewidth. In Proc. ESA (Leibniz International Proceedings in Informatics (LIPIcs)), Vol. 87. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 68:1--68:13.

[53]

Robert E. Tarjan. 1985. Decomposition by clique separators. Discrete Mathematics 55, 2 (1985), 221--232.

[54]

Robert E. Tarjan and Mihalis Yannakakis. 1984. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13, 3 (1984), 566--579.

Digital Library

Cited By

Landeta-López PGuevara-Vega C(2024)Computational Experiments in Computer Science Research: A Literature SurveyIEEE Access10.1109/ACCESS.2024.345880812(132254-132270)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3458808
Brosse CConte ALimouzy VPunzi GRucci D(2024)Output-Sensitive Enumeration of Potential Maximal Cliques in Polynomial SpaceCombinatorial Algorithms10.1007/978-3-031-63021-7_29(382-395)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-63021-7_29
Gottlob GLanzinger MLongo DOkulmus C(2023)Incremental Updates of Generalized Hypertree DecompositionsACM Journal of Experimental Algorithmics10.1145/357826627(1-28)Online publication date: 3-Mar-2023
https://dl.acm.org/doi/10.1145/3578266
Show More Cited By

Index Terms

Solving Graph Problems via Potential Maximal Cliques: An Experimental Evaluation of the Bouchitté--Todinca Algorithm
1. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming
    2. Graph algorithms analysis
  2. Theory and algorithms for application domains

Recommendations

Listing all potential maximal cliques of a graph

A potential maximal clique of a graph is a vertex set that induces a maximal clique in some minimal triangulation of that graph. It is known that if these objects can be listed in polynomial time for a class of graphs, the treewidth and the minimum fill-...
Finding Optimal Triangulations Parameterized by Edge Clique Cover
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 ( $cc$ ) to such problems. This ... $^{}$ $^{}$ $^{}^{}$ $^{}^{}$ $^{}$ $^{}^{}$ $^{}^{}$ $^{}^{}$ $^{}$ $^{}^{^{}}$ $^{}^{}$ $^{}^{^{}}$ $^{}^{^{}}$
Algorithms Parameterized by Vertex Cover and Modular Width, Through Potential Maximal Cliques

In this paper we give upper bounds on the number of minimal separators and potential maximal cliques of graphs w.r.t. two graph parameters, namely vertex cover ($${\text {vc}}$$vc) and modular width ($${\text {mw}}$$mw). We prove that for any graph, the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Journal of Experimental Algorithmics

ACM Journal of Experimental Algorithmics Volume 24, Issue

Special Issue ESA 2016, Regular Papers and Special Issue SEA 2018

2019

622 pages

ISSN:1084-6654

EISSN:1084-6654

DOI:10.1145/3310279

Issue’s Table of Contents

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 18 February 2019

Accepted: 01 December 2018

Revised: 01 October 2018

Received: 01 March 2018

Published in JEA Volume 24

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

DoCS Doctoral Programme in Computer Science and the Research Funds of the University of Helsinki
Academy of Finland

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
287
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Landeta-López PGuevara-Vega C(2024)Computational Experiments in Computer Science Research: A Literature SurveyIEEE Access10.1109/ACCESS.2024.345880812(132254-132270)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3458808
Brosse CConte ALimouzy VPunzi GRucci D(2024)Output-Sensitive Enumeration of Potential Maximal Cliques in Polynomial SpaceCombinatorial Algorithms10.1007/978-3-031-63021-7_29(382-395)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-63021-7_29
Gottlob GLanzinger MLongo DOkulmus C(2023)Incremental Updates of Generalized Hypertree DecompositionsACM Journal of Experimental Algorithmics10.1145/357826627(1-28)Online publication date: 3-Mar-2023
https://dl.acm.org/doi/10.1145/3578266
Schidler ASzeider S(2023)Computing optimal hypertree decompositions with SATArtificial Intelligence10.1016/j.artint.2023.104015325:COnline publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1016/j.artint.2023.104015
Korhonen T(2022)Finding Optimal Triangulations Parameterized by Edge Clique CoverAlgorithmica10.1007/s00453-022-00932-084:8(2242-2270)Online publication date: 5-Feb-2022
https://doi.org/10.1007/s00453-022-00932-0
Korhonen TBerg JJärvisalo M(2019)Enumerating potential maximal cliques via SAT and ASPProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367032.3367191(1116-1122)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367032.3367191

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents