Revisiting the Top-Down Computation of BDD of Spanning Trees of a Graph and Its Tutte Polynomial

Farley Soares OLIVEIRA  Hidefumi HIRAISHI  Hiroshi IMAI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E102-A   No.9   pp.1022-1027
Publication Date: 2019/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E102.A.1022
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Graph algorithms
Keyword: 
BDD,  Tutte polynomial,  graph,  pathwidth,  FPT algorithm,  

Full Text: FreePDF

Summary: 
Revisiting the Sekine-Imai-Tani top-down algorithm to compute the BDD of all spanning trees and the Tutte polynomial of a given graph, we explicitly analyze the Fixed-Parameter Tractable (FPT) time complexity with respect to its (proper) pathwidth, pw (ppw), and obtain a bound of O*(Bellmin{pw}+1,ppw}), where Belln denotes the n-th Bell number, defined as the number of partitions of a set of n elements. We further investigate the case of complete graphs in terms of Bell numbers and related combinatorics, obtaining a time complexity bound of Belln-O(n/log n).