4
Consider a graph on vertex set $V_1\cup V_2\cup V_3\cup V_4\cup \{a,b,c,d\}$ where $|V_1|=|V_2|=|V_3|=|V_4|=n$. The edge set $E$ is covered by $C=\{V_1\cup\{a,c\},V_2\cup\{a,d\},V_3\cup\{b,c\},V_4\cup\{b,d\},\{a,b\},\{c,d\}\}$.
When $n$ is large enough, any minimalist cover must contain the four maximum cliques $V_1\cup\{a,c\}$ and so on, so it is not hard ...
3
I see this question only 2.5 years after, but I think I have a relevant answer. Indeed, it is at the core of the work we have done on Fast generation of random connected graphs with prescribed degrees.
In this paper, we start with a connected graph, and perform large numbers of edge swaps in order to make it random. We however want to obtain a random ...
1
This maybe: https://papers-gamma.link/paper/32
With an open source implementation here: https://github.com/maxdan94/kClist
Only top voted, non community-wiki answers of a minimum length are eligible
Related Tags
graph-algorithms × 916graph-theory × 469
ds.algorithms × 303
cc.complexity-theory × 126
reference-request × 97
approximation-algorithms × 63
np-hardness × 62
co.combinatorics × 54
directed-acyclic-graph × 41
shortest-path × 38
optimization × 36
planar-graphs × 34
clique × 31
ds.data-structures × 28
graph-isomorphism × 25
matching × 25
time-complexity × 22
tree × 22
counting-complexity × 20
graph-colouring × 20
linear-programming × 19
parameterized-complexity × 18
treewidth × 17
fixed-parameter-tractable × 16
max-flow × 15