3
$\begingroup$

I'm not sure to what degree this is a graph problem, and algorithms question, or what, but I'll give the setup:

I have a simple undirected graph given in the form (for example) $E=\{\{v_1,v_2\},\{v_0,v_1\},\{v_0,v_2\},\{v_0,v_3\},\dots\}$ where $V=\bigcup E$ and $E$ is a set of pairs, and I wish to find a representation $K=\{\{v_0,v_1,v_2\},\{v_0,v_3\},\dots\}$ such that $E=\{x:|x|=2\wedge\exists y\in K\,x\subseteq y\}$ and $|K|$ is minimal. What can be said about this problem: How hard is it? Can it be stated in terms of more common graph problems? If possible, give an algorithm for finding such a $K$ ($K$ is not unique).

It is easily observed that $K$ represents a set of cliques in the graph, so I want to relate it to the maximal clique problem, but my goal is not necessarily to find a maximal clique, just a minimal covering set of cliques.

Edit: An alternative minimality condition is to minimize $|K|+\alpha\sum_{x\in K}|x|$, which more accurately reflects my goal of using this format as a compression system for storing such undirected graphs. In my application, $\alpha=2/7$.

$\endgroup$
3
$\begingroup$

This is known as (Edge) Clique Cover. It is NP-hard and hard to approximate. Here's a paper (of which I am a coauthor) that contains some experiments. The variant where the sum of clique sizes is maximized is also NP-hard. In my experience, choosing either objective does not make a big difference, so unless you're looking for optimal solutions, the heuristics from either paper might be good for your objective, which is a mixture of these two.

$\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.