3
$\begingroup$

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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
5
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Max Horn
    Dec 14, 2011 at 16:45
  • $\begingroup$ Max: yes, exactly. $\endgroup$
    – Łukasz Grabowski
    Dec 14, 2011 at 17:30
  • $\begingroup$ @Colin: do you know anything has been done since about the problem described in the paragraph 7.1? $\endgroup$
    – Łukasz Grabowski
    Dec 14, 2011 at 18:40
  • $\begingroup$ @Łukasz: I have no idea, sorry. $\endgroup$
    – Colin McQuillan
    Dec 14, 2011 at 18:53
3
$\begingroup$

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), "Isomorphism 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 simplicial 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Will Sawin
    Dec 14, 2011 at 17:55
  • $\begingroup$ László Babai has announced (2015 and then 2017) a quasipolynomial time algorithm for the graph isomorphism problem. History and references can be found on Wikipedia page linked above. $\endgroup$
    – Sam Nead
    Feb 7 at 16:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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