Trimmed Moebius Inversion and Graphs of Bounded Degree

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto

TL;DR

This paper introduces a "trimmed" version of Moebius inversion, a powerful combinatorial technique, to speed up computations for problems on graphs with bounded degrees. They achieve this by optimizing a classic algorithm (Yates's algorithm) to avoid unnecessary calculations, leading to improved theoretical time bounds for problems like finding the Domatic and Chromatic numbers of graphs.

What Problem Does This Paper Address?

The paper tackles the challenge of efficiently solving combinatorial optimization problems, particularly those related to set systems and graph properties. A core tool in this area is Moebius inversion, often implemented using Yates's algorithm. While Yates's algorithm is efficient for general inputs (running in $O(2^n n)$ time), it can be oblivious to the underlying structure of the problem. The authors aim to exploit structural properties, specifically bounded degrees in graphs, to achieve running times that are sub-exponential in the number of vertices ($n$), moving beyond the general $2^n$ barrier. They focus on problems like computing the number of dominating sets, packings, coverings, and partitions, and specifically on finding the Domatic Number and Chromatic Number of graphs.

Methods

The central innovation is a "trimmed" Moebius inversion technique. This builds upon Yates's algorithm by intelligently pruning the search space. Instead of computing transforms for all possible subsets, the trimmed approach focuses only on "interesting" subsets (those within the "support" of the function being transformed) and their relevant supersets or subsets. This is achieved through a careful, point-by-point evaluation that allows computations for a subset to be completed before moving to its supersets.

Key algorithmic contributions include:

  • Trimmed Pointwise Evaluation: Adapting Yates's algorithm to work with the support of the function, reducing computations by exploiting the fact that certain intermediate values will be zero.
  • Trimmed Moebius Inversion Algorithms: Developing specific algorithms (Algorithm C for covers, Algorithm D for partitions) that leverage the trimmed evaluation to compute set function properties more efficiently.
  • Intersection Theorem Application: Crucially, the paper applies a theorem by Chung et al. (1986) to bound the size of certain set families (like dominating sets or maximal independent sets) in graphs of bounded maximum degree $\Delta$. This theorem relates the size of a family to the sizes of its intersections with specific subsets, providing a critical combinatorial tool.

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and their complexity bounds, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • "Trimming" is More Than Just Pruning: The core idea is that by processing subsets in a specific order (bottom-up), we can complete calculations for a subset before needing information from its supersets. This is a significant departure from standard approaches.
  • Exploiting Structure for Sub-Exponential Time: The paper demonstrates that for graphs with bounded maximum degree $\Delta$, it's possible to break the $2^n$ barrier for problems like Chromatic Number and Domatic Number. This is achieved by combining the trimmed Moebius inversion with combinatorial bounds on set families related to graph properties.
  • The $2^n$ Barrier is Not Absolute for Sparse Graphs: The work challenges the intuition that $2^n$ is a fundamental lower bound for many combinatorial problems on general graphs. By focusing on graph structure (bounded degree), they show improvements are possible.
  • Combinatorial Bounds are Key: The effectiveness of the trimmed approach hinges on finding tight combinatorial bounds for the size of relevant set families (e.g., dominating sets, independent sets) in graphs of bounded degree. The Chung et al. intersection theorem plays a vital role here.

Key Results

The paper presents improved theoretical time bounds for several combinatorial problems on $n$-vertex graphs with maximum degree $\Delta$:

  • Domatic Number: Decidable in time $O^*((2^{\Delta+1}-2)^{\frac{n}{\Delta+1}})$. For constant $\Delta$, this is $O((2-\epsilon)^n)$ for some $\epsilon > 0$.
  • Chromatic Number (via independent sets): Decidable in time $O^*((2^{\Delta+1}-\Delta-1)^{\frac{n}{\Delta+1}})$. For constant $\Delta$, this is also $O((2-\epsilon)^n)$.
  • Number of Dominating Sets: Bounded by $(2^{\Delta+1}-1)^{\frac{n}{\Delta+1}}$.
  • Number of Maximal Independent Sets: Bounded by $O^*(1.4423^n)$.
  • Number of Maximal Induced Bipartite Subgraphs: Bounded by $O^*(1.7724^n)$.

These bounds are shown to be tight for certain graph structures, like disjoint unions of complete graphs.

Limitations and Future Work

  • Modest Improvements for Small $\Delta$: The authors acknowledge that for small values of $\Delta$, the improvements over $2^n$ are "minute."
  • Need for Further Trimming/Splitting: The paper suggests that to achieve further improvements, especially for problems like Chromatic and Domatic Number, more sophisticated techniques like further trimming or splitting the problem into connected components might be necessary.
  • Tightness of Bounds: The current bounds are met by specific graph constructions (disjoint unions of complete graphs). This implies that either the combinatorial bounds used can be tightened, or the algorithms themselves need further refinement to exploit more subtle structural properties.
  • Potential for Other Problems: The paper hints at potential applications to other problem variants, such as determining if a $\Delta$-regular graph has a domatic number of at least $\Delta/2$, suggesting that the framework is extensible.

Summary updated

Abstract

We study ways to expedite Yates's algorithm for computing the zeta and Moebius transforms of a function defined on the subset lattice. We develop a trimmed variant of Moebius inversion that proceeds point by point, finishing the calculation at a subset before considering its supersets. For an $n$-element universe $U$ and a family $scr F$ of its subsets, trimmed Moebius inversion allows us to compute the number of packings, coverings, and partitions of $U$ with $k$ sets from $scr F$ in time within a polynomial factor (in $n$) of the number of supersets of the members of $scr F$. Relying on an intersection theorem of Chung et al. (1986) to bound the sizes of set families, we apply these ideas to well-studied combinatorial optimisation problems on graphs of maximum degree $Delta$. In particular, we show how to compute the Domatic Number in time within a polynomial factor of $(2^{Delta+1-2)^{n/(Delta+1)$ and the Chromatic Number in time within a polynomial factor of $(2^{Delta+1-Delta-1)^{n/(Delta+1)$. For any constant $Delta$, these bounds are $O bigl((2-epsilon)^n bigr)$ for $epsilon>0$ independent of the number of vertices $n$.
BibTeX
@article{bjorklund2010trimmed,
  author = {Andreas Björklund and Thore Husfeldt and Petteri Kaski and Mikko Koivisto},
  title = {{Trimmed Moebius Inversion and Graphs of Bounded Degree}},
  journal = {Theory Comput. Syst.},
  year = {2010},
  doi = {10.1007/s00224-009-9185-7},
}

Loading related content...

Figure