3
$\begingroup$

I'm facing a graph problem and I'm looking to identify it, maybe as a special case of a more general problem, so that I can then find an approximation algorithm for its solution (I'm assuming it's NP-complete).

I have a graph $G$ with $|V|$ vertices. Every vertex has at least one edge connected to it. I want to find the induced subgraphs of $G$ of order $\leq k$, where every edge in $G$ is found in at least one subgraph and the number of subgraphs is minimized. I can assume as a pre-condition that a solution exists (there exist no cliques with order $>k$).

For example, here is a graph $G$ with 5 vertices. If $k=4$, there's no solution with 1 subgraph since there are more than 4 vertices in $G$. A solution for $k=4$ with 2 subgraphs is shown beside it:

enter image description here

The order of each subgraph can be less than $k$, so $\{\{1, 2, 3\},\{1, 2, 4, 5\}\}$ is another valid solution.

This is not a solution because the black edge between $2$ and $3$ is not covered by either subgraph:

enter image description here

All I'm looking for is a name for the problem, if it exists, so that I can research it and hopefully find an approximation algorithm. Having subgraph order $\leq k$ is a hard requirement but the "minimum number of subgraphs" part can be approximated as long as it's close to minium.

$\endgroup$
1
$\begingroup$

Your problem is known as $k$-clique cover. Goldschmidt, Hochbaum, Hurkens and Yu describe several approximation algorithms in their paper Approximation algorithms for the $k$-clique covering problem. The paper is from 1995, so there are likely newer works on this topic, which you can find by scanning the papers citing this paper.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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