# Are there any results on the following “generalized matching” problems?

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?

• 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 – JimN Sep 10 '16 at 4:33

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.