Given a graph $G = (V, E)$, one can view a matching $M$ on the graph as a partition of $V$ into vertex sets $S_{i, j}$ for $j \in \{1, 2\}$, where each $S_{i, j}$ induces a subgraph in $G$ isomorphic to $K_{j}$. That is, the edges in $M$ correspond to subgraphs isomorphic to $K_{2}$ and the leftover (unmatched) vertices correspond to subgraphs isomorphic to $K_{1}$. A matching algorithm can then be viewed as partitioning the vertex set into subsets which induce complete graphs, where we try to include as many $K_{2}$s as possible before resorting to $K_{1}$.

I'm interested in a generalization of this problem where $j$ is as large as possible (or perhaps some fixed j > 2, if there are nice results). In particular, I'd like an algorithm which first tries to find subsets of $V$ which induce subgraphs isomorphic to $K_{l}$, for $l$ as large as possible, and then $K_{l-1}$, etc.

Is there any work on problems like this?

  • 3
    $\begingroup$ with $l$ even at 3, you are dealing with an NP-complete problem, even when the graph is 3-partite. See profs.sci.univr.it/~rrizzi/classes/Complexity/provette/Mirko/… for instance. There is a lot of literature on triangle covers or clique covers, and you are interested in the vertex-disjoint flavour of these $\endgroup$
    – JimN
    Sep 10, 2016 at 4:33

1 Answer 1


In http://www.sciencedirect.com/science/article/pii/S0012365X13003543 , we use exactly this process of picking the largest possible clique, then the next largest available clique, and so on (without repeating any vertices). When applied to a cograph $G$, this algorithm forms a cluster graph subgraph of $G$ with the max number of edges possible. The paper contains some combinatorial results on sizes of cliques obtained during such a process.

This paper http://publicaciones.dc.uba.ar/Publications/2015/BDNV15/BDNV15.pdf generalizes our result to a class of graphs beyond cographs.

I'm not sure which way you want to generalize matchings ... towards triangle covers or clique covers, but either way, it seems you will be moving from P-territory into NP-complete land. Unless you restrict your initial graph to certain structural classes.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.