8
$\begingroup$

In order theory, an antichain (Sperner family/clutter) is a subset of a partially-ordered set, with the property that no two elements are comparable with each other. A maximal antichain is the antichain which is not properly contained in another antichain. Let's take the power set of $\{1,2,\ldots, n\}$ as our partially-ordered set, here the order is given by inclusion. Then my question is, for any given antichain of this partially-orded set, is there any polynomial-time algorithm (with respect to $n$) to verify that this antichain is indeed "maximal"? In other words, verifying that any subset of $\{1,2,\ldots, n\}$ is either contained in, or contains some set from the antichain. Here such algorithm should have polynomial run-time for ANY antichain.

Update: To clarify, here I will treat the size of our antichain as the parameter for the verification algorithm. In other words, my question is: does there exist a verification algorithm, whose run-time is polynomial in $n$ and $m$, where $m$ is the size of the antichain. When the size of our antichain $m$ is exponential in $n$ then such algorithm is trivial (just comparing those elements one by one); but when the given antichain has O(poly(n)) size, this is my interested case. For example, when the antichain is given by $\{\{1\}, \ldots, \{n\}\}$, we certainly do not have to do the brute force comparison.

$\endgroup$
5
  • 4
    $\begingroup$ But the antichain itself normally contains exponentially many sets, how do you mean to treat them all in polynomial time? $\endgroup$ – Fedor Petrov Jan 18 at 13:03
  • $\begingroup$ Yeah good question. I'm thinking of the poset as the power set of $\{1,2,\ldots, n\}$, therefore it has 2^n many elements, and like you said, antichain of this poset can also contain exponentially many elements. I will revise the question as the following: does there exist a verification algorithm, whose run-time is polynomial in $n$ and $m$, where $m$ is the size of the antichain. When the size of our antichain is exponential then such algorithm is trivial (just comparing those elements one by one); but when the given antichain has O(poly(n)) size, this is my interested case. $\endgroup$ – HAORAN ZHU Jan 18 at 13:34
  • 1
    $\begingroup$ For example, when the antichain is given by $\{\{1\}, \ldots, \{n\}\}$ which is $n$ singletons, then this antichain is maximal, and we certainly do not have to do the brute-force comparison. $\endgroup$ – HAORAN ZHU Jan 18 at 13:34
  • $\begingroup$ There is an action of the symmetric group on the whole thing which might be used to reduce complexity $\endgroup$ – მამუკა ჯიბლაძე Jan 26 at 17:45
  • $\begingroup$ See also mathoverflow.net/q/358303/41291 $\endgroup$ – მამუკა ჯიბლაძე Jan 26 at 17:48
2
$\begingroup$

Remark. Originally I claimed this to be a full solution, but that was false, as shown by Emil in the comments. However, this argument proves the following weaker version.

I can prove that it is co-NP-complete to decide for an input family $A$ whether there is a set $S$ that is unrelated to all sets in $A$. I'll call such families maximal. This shows that any possible polynomial time algorithm must exploit that the input family is an antichain, already for linear sized inputs. My reduction is from SAT.

Given a CNF $\Psi$ on $n$ variables, we convert it into a family $A$ over $2n$ elements, such that $A$ is maximal if and only if $\Psi$ in unsatisfiable. The $2n$ elements will come in pairs, which I denote by $i$ and $i'$.
The complement of every pair is contained in $A$ regardless of $\Psi$, so $\overline{11'}\in A$, $\overline{22'}\in A$, ..., $\overline{nn'}\in A$.
Moreover, for every clause we add a set to $A$ such that if $x_i$ is in the clause, the set contains $i$, while if $\bar x_i$ is in the clause, the set contains $i'$. For example, the clause $(x_i\vee \bar x_j)$ adds the set $ij'$ to $A$.

Suppose $\Psi$ is satisfiable. Then for a satisfying evaluation $x$, define the set $S$ such that $i\in S$ if $x_i$ is false and $i'\in S$ if $x_i$ is true. It is straight-forward to check that $S$ is not in relation with any element of $A$.

Suppose that $A$ is not maximal. Take a set $S$ not in relation with any element of $A$. Define $x_i$ to be true if $i\notin S$ and false if $i'\notin S$, otherwise arbitrarily. This definition is indeed correct, as $\overline{ii'}\in A$ implies that $i,i'\in S$ is not possible. It is straight-forward to check that $x$ is a satisfying evaluation of $\Psi$.

$\endgroup$
6
  • 1
    $\begingroup$ Can you elaborate why $x$ is a satisfying assignment? In particular, let $C$ be a clause such that no literal from $C$ nor its negation is in $S$; then $x$ restricted to $C$ was chosen purely “arbitrarily”. So why should it necessarily satisfy $C$? $\endgroup$ – Emil Jeřábek Jan 20 at 9:07
  • $\begingroup$ It took me a moment to parse, so, just to make sure: the underlying poset here is $2^{2n}$, and the order is containment? $\endgroup$ – LSpice Jan 20 at 9:28
  • 2
    $\begingroup$ @LSpice The question already specifies that the poset is a powerset ordered by inclusion. $\endgroup$ – Emil Jeřábek Jan 20 at 9:32
  • 2
    $\begingroup$ Here is an explicit counterexample. Let $\Psi$ be $(x\lor y)\land(x\lor u)\land(x\lor v)$, $S=\{u,v\}$, and fix the assignment so that it falsifies $x$ and $y$. $\endgroup$ – Emil Jeřábek Jan 20 at 9:38
  • 2
    $\begingroup$ Under the new definition, $A$ is not an antichain (unless all clauses have $n$ literals, in which case satisfiability can be decided in polynomial time). $\endgroup$ – Emil Jeřábek Jan 20 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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