<p>In <a href="http://www.sciencedirect.com/science/article/pii/S0012365X13003543" rel="nofollow">http://www.sciencedirect.com/science/article/pii/S0012365X13003543</a> , 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.</p>

<p>This paper <a href="http://publicaciones.dc.uba.ar/Publications/2015/BDNV15/BDNV15.pdf" rel="nofollow">http://publicaciones.dc.uba.ar/Publications/2015/BDNV15/BDNV15.pdf</a> generalizes our result to a class of graphs beyond cographs.</p>

<p>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.</p>

CC BY-SA 3.0
2016-09-10T04:50:10.600Z
2016-09-10T04:50:10.600Z
JimN
<p>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}$.</p>

<p>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.</p>

<p>Is there any work on problems like this?</p>

CC BY-SA 3.0
2016-09-10T04:33:24.017Z
with $l$ even at 3, you are dealing with an NP-complete problem, even when the graph is 3-partite. See http://profs.sci.univr.it/~rrizzi/classes/Complexity/provette/Mirko/pt_fine.pdf 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
<graph-theory><graph-algorithms><matching>
Are there any results on the following "generalized matching" problems?
FlagCapper
# Are there any results on the following "generalized matching" problems?

(Asked by: username_0 on 2016-09-09)

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?

**Tags:** graph-theory, graph-algorithms, matching

> **Comments:**
> **username_1**: with $l$ even at 3, you are dealing with an NP-complete problem, even when the graph is 3-partite. See http://profs.sci.univr.it/~rrizzi/classes/Complexity/provette/Mirko/pt_fine.pdf 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  

---

## 1 answers

### Answer by username_1 on 2016-09-10. Score: 3 | Accepted answer

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.


---

