Suppose I have a collection of $m$ subsets of $\{1,\dots,n\}$, all of size $k$. I want to list these subsets so that two subsets adjacent to one another in the list are as close to one another as possible in that their intersection is as small in cardinality as possible. Can I do this in $o(m^2)$ time?
$\begingroup$
$\endgroup$
8
-
4$\begingroup$ I think the question needs more specificity. What is the cost function of an ordering $S_1, S_2, \ldots, S_m$? Is it $\sum_i | S_i \oplus S_{i+1} |$? Is it $\max_i | S_i \oplus S_{i+1} |$? Something else? $\endgroup$– mikeroNov 21, 2011 at 19:56
-
$\begingroup$ @mikero If someone can answer the question with respect to any of the cost functions that you mentioned, that would be great. $\endgroup$– Craig FeinsteinNov 21, 2011 at 21:18
-
2$\begingroup$ Maybe you mean "intersection is as LARGE in cardinality as possible" ? And why do you think even m^2 is possible ? or m^3 ? or any polynomial in $m$ - after all, this sounds like a TSP-style problem. $\endgroup$– Suresh VenkatNov 21, 2011 at 22:39
-
$\begingroup$ I think some motivation about why you are interested in this problem would be helpful. $\endgroup$– KavehNov 22, 2011 at 0:34
-
3$\begingroup$ Based on the comments on @mikero's answer, I think maybe your question is as follows ? you're given $m$ objects (that happen to be size-$k$ subsets of a universe) and a way to compare them, and you want to then "sort" them ? If that's the case, then you can clearly do this in m log m comparisons (where a comparison might take $k$ time). but your original question is definitely resolved by mikero's answer. $\endgroup$– Suresh VenkatNov 22, 2011 at 3:53
|
Show 3 more comments
2 Answers
$\begingroup$
$\endgroup$
6
Without knowing any further restrictions on the parameters, the problem is NP-hard.
Let $G = (V,E)$ be an undirected graph. For $v \in V$, define the set $S_v = \{ e \mid e \in E \mbox{ is incident to } v\}$. Then $| S_u \cap S_v | = 1$ if $u$ and $v$ are adjacent, and $|S_u \cap S_v| = 0$ otherwise. You can pad out each $S_v$ with distinct junk items until each set has the same size. Then an ordering of $\{ S_v \mid v \in V\}$ in which adjacent sets have "as large an intersection as possible" corresponds to a Hamiltonian path in $G$ (for sensible measures like maximizing $\sum_i |S_i \cap S_{i+1}|$ or maximizing $\min_i |S_i \cap S_{i+1}|$).
If you want adjacent sets to have "as small an intersection as possible", simply complement each of these sets and the same reduction also works.
Your question suggests that you think this problem can be done in $O(m^2)$, and now I'm curious why.
-
$\begingroup$ This doesn't answer my question, and the problem is not NP-complete. $m$ is the number of subsets of size $k$ given as input in the problem. I'm trying to "sort" these subsets in $o(m^2)$ time. Can it be done? $\endgroup$ Nov 21, 2011 at 23:56
-
1$\begingroup$ I do not see a problem with mikero's answer. In his problem, the input is $|V|$ sets each of size equal to the max degree of $G$. Then the problem is NP-hard for either of the objectives named. I think you're mistakenly thinking that greedy works, but it doesn't. $\endgroup$ Nov 22, 2011 at 3:17
-
$\begingroup$ I agree that you can convert the problem into a $k$-regular graph with $m$ vertices. Then if the edges were weighted with the cardinality of the intersection of the sets that the vertices represent, you would get a traveling salesman type of problem; however, the graph and weights on the edges have a special structure so it's not clear to me that the problem is $NP$-hard. $\endgroup$ Nov 22, 2011 at 13:42
-
$\begingroup$ As a example which indicates to me that the problem is not NP-hard, suppose that $m=2^n$ and the subsets are all the subsets of $\{1,\dots,n\}$. Then the solution to this problem can be found in Gray codes. $\endgroup$ Nov 22, 2011 at 14:23
-
2$\begingroup$ @mikero, now I see your intuition. I was blinded by my unfounded belief that this could be done in $\Theta(m^2)$ time. Very good job. Thank you. $\endgroup$ Nov 22, 2011 at 16:42
$\begingroup$
$\endgroup$
Although mikero proved that your problem is hard, there is a fast general algorithm that gives reasonably good solutions to this kind of problem (where you want an ordering of a set of "objects" such that if two are consecutive then they are "similar").
The result is as follows: given any connected graph, in linear time we can find a cyclic ordering of its vertices such that if two are consecutive then they are at distance $\leq 3$ in the graph.
It's an simple but non-trivial algorithm: first take a spanning tree, then apply a function called prepostorder to it, and we're done.
Prepostorder (in Haskell) is:
data Tree = Root Nat [Tree]
prepost (Root r xs):ys = [r] ++ postpre xs ++ prepost ys
prepost [] = []
postpre (Root r xs):ys = prepost xs ++ [r] ++ postpre ys
postpre [] = []
This is taken from TAOCP section 7.2.1.6, and in particular implies that the cube of any connected graph is hamiltonian.
