Khmelnitskaya et al. have recently proposed the average covering tree value as a new solution concept for cooperative transferable utility games with directed graph structure. The average covering tree value is defined as the average of marginal contribution vectors corresponding to the specific set of rooted trees, and coincides with the Shapley value when the game has complete communication structure. In this paper, we discuss the computational complexity of the average covering tree value. We show that computation of the average covering tree value is #P-complete even if the characteristic function of the game is {0,1}-valued. We prove this by a reduction from counting the number of all linear extensions of a partial order, which has been shown by Brightwell et al. to be a #P-complete counting problem. The implication of this result is that an efficient algorithm to calculate the average covering tree value is unlikely to exist. © 2013 Operations Research Society of China, Periodicals Agency of Shanghai University, and Springer-Verlag Berlin Heidelberg.