An Experimental Approach to Exact and Random Boolean-Widths and Their Comparison with Other Width Parameters. (16th June 2021)

• Record Type: Journal Article
• Authors: Sharmin, Sadia
• Is Part Of: Computer journal. Volume 65:Number 9(2022)
• Page Start: 2392
• Page End: 2399
• Publication Date: 2021-06-16
• Subjects: boolean-width -- tree-width -- rank-width -- random decomposition -- unions of neighborhood; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxab073
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: Parameterized complexity is an exemplary approach that extracts and exploits the power of the hidden structures of input instances to solve hard problems. The tree-width ($tw$ ), path-width ($pathw$ ), branch-width ($bw$ ), clique-width ($cw$ ), rank-width ($rw$ ) and boolean-width ($boolw$ ) are some width measures of graphs that are used as parameters. Applications of these width parameters show that dynamic programming algorithms based on a path, tree or branch decomposition can be an alternative to other existing techniques for solving hard combinatorial problems on graphs. A large number of the linear- or polynomial-time fixed parameter tractability algorithms for problems on graphs start by computing a decomposition tree of the graph with a small width. The focus of this paper is to study the exact and random boolean-widths for special graphs, real-world graphs and random graphs, as well as to check their competency compared with several other existing width parameters. In our experiments, we use graphs from TreewidthLIB, which is a set of named graphs and random graphs generated by the Erdös–Rényi model. Until now, only very limited experimental work has been carried out to determine the exact and random boolean-widths of graphs. Moreover, there are no approximation algorithms for computing the near-optimal boolean-width of a given graph. The results of this paper demonstrate that the boolean-width can be used not only in theory but also in practice and is competitive with other width parameters for real graphs.