patternMinor
Is this problem NP-hard? Maximizing selected sets so that their union is less than k?
Viewed 0 times
thisproblemunionthanhardmaximizingthatselectedlesssets
Problem
There is an NP-hard problem called Minimum k-Union where we are given a set system with $n$ sets and are asked to select $k$ sets in order to minimize the size of their union.
I'm currently interested in a very similar problem, but don't know how to convert one to another:
Given a set system with $n$ sets and a bound $k$. Select as many sets as possible while their union is at most $k$.
Is this problem NP-hard? Any hint is welcome!
Updated 2020: I found a paper called "Unbalanced Graph Cuts" by Hayrapetyan et al. [ESA'05] which describes the Minimum-size bounded-capacity cut (MinSBCC) problem which is very similar to what I looked for.
I'm currently interested in a very similar problem, but don't know how to convert one to another:
Given a set system with $n$ sets and a bound $k$. Select as many sets as possible while their union is at most $k$.
Is this problem NP-hard? Any hint is welcome!
Updated 2020: I found a paper called "Unbalanced Graph Cuts" by Hayrapetyan et al. [ESA'05] which describes the Minimum-size bounded-capacity cut (MinSBCC) problem which is very similar to what I looked for.
Solution
Very easy. Clique problem reduces to yours.
Each set is the 2-element edges $\{u,v\}$ of $G$.
A $k$-clique has as many edges as possible while only involves $k$ vertices. So, $K={k \choose 2}$.
Each set is the 2-element edges $\{u,v\}$ of $G$.
A $k$-clique has as many edges as possible while only involves $k$ vertices. So, $K={k \choose 2}$.
Context
StackExchange Computer Science Q#96272, answer score: 2
Revisions (0)
No revisions yet.