<p>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").</p>

<p>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.</p>

<p>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.</p>

<p>Prepostorder (in Haskell) is:</p>

<blockquote>
  <p>data Tree = Root Nat [Tree]</p>
  
  <p>prepost (Root r xs):ys = [r] ++ postpre xs ++ prepost ys</p>
  
  <p>prepost [] = []</p>
  
  <p>postpre (Root r xs):ys = prepost xs ++ [r] ++ postpre ys</p>
  
  <p>postpre [] = []</p>
</blockquote>

<p>This is taken from TAOCP section 7.2.1.6, and in particular implies that the cube of any connected graph is hamiltonian.</p>

CC BY-SA 3.0
2011-11-23T07:27:05.387Z
2011-11-23T07:27:05.387Z
didest
<p>Without knowing any further restrictions on the parameters, the problem is NP-hard.</p>

<p>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}|$).</p>

<p>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.</p>

<p>Your question suggests that you think this problem can be done in $O(m^2)$, and now I'm curious why.</p>

CC BY-SA 3.0
2011-11-21T23:56:13.110Z
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?
Craig Feinstein
CC BY-SA 3.0
2011-11-22T03:17:09.207Z
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.
Sasho Nikolov
CC BY-SA 3.0
2011-11-22T13:42:26.683Z
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.
Craig Feinstein
CC BY-SA 3.0
2011-11-22T14:23:12.077Z
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.
Craig Feinstein
CC BY-SA 3.0
2011-11-22T15:33:08.943Z
@CraigFeinstein: my response takes an arbitrary graph and converts it into an instance of your subset-ordering problem, not the other way around.
mikero
CC BY-SA 3.0
2011-11-22T16:42:14.437Z
@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.
Craig Feinstein
CC BY-SA 3.0
2011-11-21T23:47:54.797Z
2011-11-21T23:47:54.797Z
mikero
<p>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?</p>

CC BY-SA 3.0
2011-11-21T19:56:35.410Z
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?
mikero
CC BY-SA 3.0
2011-11-21T21:18:46.443Z
@mikero If someone can answer the question with respect to any of the cost functions that you mentioned, that would be great.
Craig Feinstein
CC BY-SA 3.0
2011-11-21T22:39:39.770Z
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.
Suresh Venkat
CC BY-SA 3.0
2011-11-22T00:34:13.270Z
I think some motivation about why you are interested in this problem would be helpful.
Kaveh
CC BY-SA 3.0
2011-11-22T00:49:47.653Z
@Kaveh, I was thinking about applying the idea of Gray codes for sorting $m$ subsets of size $k$, where $k<n$. $m$ could be exponential as a function of $n$.
Craig Feinstein
CC BY-SA 3.0
2011-11-22T03:53:55.810Z
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.
Suresh Venkat
CC BY-SA 3.0
2011-11-22T12:07:58.613Z
@Suresh, the "sorting" is constrained 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. Therefore, it's not clear that you can "sort" them in $m \log m$ time.
Craig Feinstein
CC BY-SA 3.0
2011-11-22T16:27:45.960Z
@suresh, Now, I realize that I meant to say that the intersection should be as large as possible, as this goes with the intuition "as close to one another as possible".
Craig Feinstein
<cc.complexity-theory>
Optimally listing of subsets
Craig Feinstein
# Optimally listing of subsets

(Asked by: username_0 on 2011-11-21)

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?

**Tags:** cc.complexity-theory
> **Comments:**
> **username_1**: 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?  
> **username_0**: @mikero If someone can answer the question with respect to any of the cost functions that you mentioned, that would be great.  
> **username_2**: 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.  
> **username_3**: I think some motivation about why you are interested in this problem would be helpful.  
> **username_0**: @Kaveh, I was thinking about applying the idea of Gray codes for sorting $m$ subsets of size $k$, where $k<n$. $m$ could be exponential as a function of $n$.  
> **username_2**: 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.  
> **username_0**: @Suresh, the "sorting" is constrained 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. Therefore, it's not clear that you can "sort" them in $m \log m$ time.  
> **username_0**: @suresh, Now, I realize that I meant to say that the intersection should be as large as possible, as this goes with the intuition "as close to one another as possible".  

---

## 2 answers

### Answer by username_1 on 2011-11-21. Score: 9 | Accepted answer

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.

> **Comments:**
> **username_0**: 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?  
> **username_5**: 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.  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_1**: @CraigFeinstein: my response takes an arbitrary graph and converts it into an instance of your subset-ordering problem, not the other way around.  
> **username_0**: @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.  

---

### Answer by username_4 on 2011-11-23. Score: 2

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.


---

