Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a set $A$ of subsets of $\{1, \ldots n\}$ which is closed under taking subsets, let $X(A)$ be the corresponding simplicial complex, i.e. simplices of $X(A)$ are elements of the set $\bar A$, and gluing is induced by containment of subsets)

Consider the following computational problem

Input: a natural number $n$ and two sets $A$ and $B$ of subsets of $\{1,\ldots, n\}$, closed under taking subsets.

Problem: Are $X(A)$ and $X(B)$ isomorphic as simplicial complexes? (i.e. is there a bijection of $\{1,\ldots ,n}$ which bijectively sends faces of $X(A)$ to faces of $X(B)$?)

Question: I'm interested to know what algorithms are known for this problem. I'm specifically interested in worst running times in terms of $n$ alone. Please note that the size of the input can be exponential in $n$.

In principle $A$ and $B$ might consist of $2^n$ subsets, so this is a lower bound for the problem, because the algorithm needs to read the input.

On the other hand the trivial algorithm of checking each permutation takes at most $\mathcal O(2^n\cdot n!)$ steps.

share|improve this question

2 Answers 2

up vote 5 down vote accepted

An exp(O(n)) algorithm is given in "Hypergraph isomorphism and structural equivalence of boolean functions", Eugene M. Luks, STOC 1999.

share|improve this answer
    
Aha, great reference! Hm, $e^{O(n)}=2^{cn}$ for a suitable constant $c$, while the naive brute force approach in $O(2^n\cdot n!)$ would amount roughly to $2^{dn\log(n)}$ (for some other constant $d$), I think? –  Max Horn Dec 14 '11 at 16:45
    
Max: yes, exactly. –  Łukasz Grabowski Dec 14 '11 at 17:30
    
@Colin: do you know anything has been done since about the problem described in the paragraph 7.1? –  Łukasz Grabowski Dec 14 '11 at 18:40
    
@Łukasz: I have no idea, sorry. –  Colin McQuillan Dec 14 '11 at 18:53

A special case of this problem is the graph isomorphism problem. Interestingly, for this it is unknown whether it is solvable in polynomial time (relative to the number of vertices, so $n$ in your case), and also unknown whether or not it is $NP$-complete. As far as I know, Luks' algorithm is still state of the art (though I might be wrong), and that has runtime $O(2^{\sqrt{n \log(n)}})$.

Since this is a special case of your problem, its general worst case runtime will be unknown, too. Of course in this special case, one has only subsets of size 2 / simplices of dimension 1; as you point out, as soon as we allow arbitrary rank simplices, the above runtime cannot be achieved anymore, as the input alone has size $O(2^n)$.

EDIT: Actually, looking at the Wikipedia link I give, I discovered that there is a paper by Babai and Codenotti (2008), "Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time", where they give an algorithm that works in the same general time as Luks' algorithm for hypergraphs (and thus in particular simplical complexes) of bounded rank that has roughly the same general run time as Luks' algorithm for graph isomorphism. Of course that still does not answer the general question.

share|improve this answer
    
If the simplicial complexes are relatively sparse one could write them in $O(nk)$, where $k$ is the number of maximal simplices. $k$ is probably bounded by $n$ choose $n/2$, but could be much lower. –  Will Sawin Dec 14 '11 at 17:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.