An Experimental Approach to Exact and Random Boolean-Widths and Their Comparison with Other Width Parameters. (16th June 2021) - Sharmin, Sadia
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.