On the triangle clique cover and Kt clique cover problems

Hoang Dau, Olgica Milenkovic, Gregory J. Puleo

TL;DR

This paper generalizes the classic problem of covering a graph's edges with cliques to the broader problem of covering all $t$-vertex cliques ($K_t$) with a minimum set of larger cliques. The authors prove a tight upper bound for covering triangles ($t=3$), provide a polynomial-time algorithm for a new class of "semichordal" graphs, and demonstrate that the general problem remains NP-hard.

What Problem Does This Paper Address?

In graph theory, a "clique cover" is a collection of cliques (complete subgraphs) that together contain every element of a specific set. Traditionally, researchers have focused on vertex clique covers (covering all nodes) and edge clique covers (covering all links).

However, modern network science has revealed that complex networks are often built from "motifs"—small, recurring patterns like triangles. If we want to understand community structures where groups are defined by these higher-order motifs rather than just individual edges, we need to solve the $K_t$ clique cover problem: what is the minimum number of cliques needed to cover every $t$-clique in a graph?

The authors aim to bridge the gap between classical results (like the 1966 Erdős-Goodman-Pósa theorem for edges) and the relatively unexplored territory of covering triangles and larger cliques.

Methods

The paper employs a mix of extremal graph theory and algorithmic design:

  • Inductive Proofs: To establish upper bounds, the authors use induction on the number of vertices ($n$), specifically looking at how removing a vertex of minimum degree affects the clique cover number.
  • Turán Graph Analysis: They compare general graphs against Turán graphs—complete multipartite graphs where parts are as equal in size as possible—which often serve as the "worst-case" or extremal examples in these problems.
  • Elimination Orderings: To develop algorithms, they utilize the concept of vertex elimination orderings. While "chordal" graphs are defined by having a simplicial elimination ordering (where neighbors of a vertex form a clique), the authors define a broader class called semichordal graphs using a $\{P_3\}$-elimination ordering.
  • Linear Programming Duality: The algorithm for semichordal graphs leverages the relationship between clique covers and clique packings (the dual problem) to ensure optimality.

Datasets

As a theoretical mathematics and computer science paper, no empirical datasets were used. The results are proven for all graphs within the specified classes (general graphs, semichordal graphs, etc.).

Key Insights and Ideas

  • The Turán Connection: The authors prove that for any graph with $n$ vertices, the number of cliques needed to cover all triangles is at most the number of triangles in the Turán graph $T(n, 3)$. This confirms that Turán graphs are the unique extremal cases for triangle covers, mirroring the classical result for edges.
  • Graphs vs. Hypergraphs: While a $K_t$ clique cover can be viewed as an edge cover in a $t$-uniform hypergraph, the authors show that graph-specific properties allow for much tighter bounds. General hypergraph theorems (like Lehel’s) provide bounds that are "strictly worse" because they don't account for the specific way cliques overlap in a standard graph.
  • Semichordal Graphs: The introduction of "semichordal" graphs is a significant contribution. This class includes all chordal graphs and all cycles ($C_n$), providing a much larger playground where the $K_t$ clique cover problem can be solved efficiently.
  • NP-Hardness: By extending a reduction technique from the 1970s, they prove that determining the $K_t$ clique cover number is NP-hard for any $t \geq 2$. This justifies the focus on specific graph classes like semichordal graphs for practical applications.

Key Results

  • Theorem 3 (The Main Result): For any graph $G$, the triangle clique cover number $\theta_\Delta(G) \leq k_3(T(n, 3))$. Equality holds if and only if $G$ is the Turán graph $T(n, 3)$.
  • Algorithm 1: A recursive polynomial-time algorithm that solves the weighted $K_t$ clique cover problem for semichordal graphs.
  • Complexity: Formal proof that the $K_t$ clique cover problem is NP-complete for any constant $t \geq 1$.
  • Improved Edge Bounds: Along the way, they derived new upper bounds for the classical edge clique cover number based on the minimum degree of the graph ($\delta(G)$), which are sharper than previous bounds in certain regimes.

Limitations and Future Work

  • The $t > 3$ Conjecture: While the authors proved the tight bound for triangles ($t=3$), they leave the general case for $t > 3$ as an open conjecture (Conjecture 1). They suspect Turán graphs $T(n, t)$ are always the extremal cases, but the proof becomes significantly more complex as $t$ increases due to the explosion of possible clique configurations.
  • Characterization of Semichordal Graphs: The authors note that while they have a sufficient condition for a graph to be semichordal (the absence of a "3-wheel"), a full characterization based on forbidden induced subgraphs remains unknown.
  • Approximation Algorithms: Given the NP-hardness for general graphs, the paper suggests that exploring approximation algorithms for the $K_t$ cover problem would be a valuable next step for large-scale network analysis.

Summary updated

BibTeX
@inproceedings{dau2019triangle,
  author = {Hoang Dau and Olgica Milenkovic and Gregory J. Puleo},
  title = {{On the triangle clique cover and Kt clique cover problems}},
  booktitle = {Discrete},
  year = {2019},
  doi = {10.1016/j.disc.2019.111627},
}
Figure