# Tag Info

14

Your problem is known in the learning literature as "learning monotone functions using membership queries". A class of monotone functions for which one can identify all minterms is known as "polynomially learnable using membership queries". It seems that the existence of a polynomial time algorithm is still open. Schmulevich et al. prove that "Almost all ...

9

Your problem is known under the name MINIMUM DIRECTED BANDWIDTH. It is NP-complete: M.R. Garey, R.L. Graham, D.S. Johnson and D.E. Knuth: "Complexity Results for Bandwidth Minimization" SIAM Journal on Applied Mathematics 34, (1978), pp. 477-495 It is problem [GT41] in the NP-completeness book by Garey and Johnson. The special case where every ...

9

I think this problem is NP-hard. I try to sketch a reduction from MinSAT. In the MinSAT problem we are given a CNF and our goal is to minimize the number of satisfied clauses. This problem is NP-hard, see e.g., http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec Divide the vertices into two groups - some will represent literals, the ...

8

As Yury already mentioned, the output size can be too large to hope for subquadratic time, when measured as a function of the input size $n$. But even when the output size is small, very little can be done. In particular, suppose that the input is a partial order with a single comparable pair, chosen uniformly at random among all such partial orders. Then ...

8

Here is an attempt to prove that the problem without the reverse condition is NP-hard. The basic idea is that disjoint intervals in $S$ like this one: [S] +-a-+ +-b-+ +---c-----+ c<a, c<b (here < is interval inclusion) can have a valid mapping to a "pyramid" in $T$: [T] +-x-+ f(a)=x, f(b)=y, f(c)=z +-y---+ +-z-----...

7

With Charles Paperman we have been able to obtain such a result for DAGs labeled with the alphabet $\{a, b\}$. Essentially, we can show that given a DAG $G$ that has large antichains of $a$-labeled elements, large antichains of $b$-labeled elements, but no large antichains containing both many $a$-labeled and $b$-labeled elements, then there is a ...

7

Restrictions on pre-orders You've described that you would like to assert restrictions on a given pre-order: for instance, that specifically $a < b$ rather than merely $a \leqslant b$, so that it would not be compatible with a pre-order in which $a \cong b$ (that is $a \leqslant b$ and $b \leqslant a$). We can achieve this by supplementing the pre-order ...

7

In their paper Every Poset Has a Central Element, Linial and Saks show (Theorem 1) that the number of queries required to solve the ideal identification problem in a poset $X$ is at most $K_0 \log_2 i(X)$, where $K_0 = 1/(2 - \log_2(1 + \log_2 5))$ and $i(X)$ is the number of ideals of $X$. What they call an "ideal" is actually a lower set and there is an ...

7

This is not a complete answer, but it's too long to be a comment. I think I found an example for which the bound $\lceil \log_2 N_X \rceil$ is not tight. Consider the following poset. The ground set is $X=\{a_1, a_2, b_1, b_2\}$, and $a_i$ is smaller than $b_j$ for all $i,j\in\{1,2\}$. The other pairs are incomparable. (The Hasse diagram is a $4$-cycle). ...

7

This problem is sometimes called Subset Containment and it is computationally equivalent to: given $n$ sets $S_1,\ldots,S_n \subseteq [d]$, are there $i \neq j$ such that $S_i \cap S_j = \varnothing$? (I believe the reduction is folklore and appears in several places, but one concrete reference is the arxiv paper "Into the Square".) In turn, this ...

6

Graph isomorphism is GI-complete for DAGs: https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Complexity_class_GI. The problem for partial orders is also GI-complete: We can reduce bipartite graph isomorphism (which is GI-complete) to 2 instances of DAG isomorphism where the DAG equals its transitive closure by considering two canonical ways to turn a ...

5

For the problem of finding all the maximal elements of $P$ over the lattice of subsets $2^{[n]}$, this amounts to exact inference of a positive boolean function of $n$ boolean variables. If you only care about the number of evaluations of $P$ (not the computational complexity), you can find a survey in Data Mining and Knowledge Discovery via Logic-Based ...

5

For the Boolean n-cube $(\{0, 1\}^n, \leq)$ (or, equivalently, for the poset $(2^S, \subseteq)$ of all subsets of an n-element set), the answer is given by Korobkov and Hansel's theorems (from 1963 and 1966, respectively). Hansel's theorem  states that an unknown monotone Boolean function (i.e., an unknown monotone predicate on this poset) can be learned ...

4

The problem is strongly NP-complete. Reduction from 3-partition, a strongly NP-complete problem. The multiset $S$, $|S| = 3m$, $\sum_{x \in S} x = n$ can be partitioned into tuples of size three of equal sum if and only if $A \leq B$ where $A = S$ and $B$ is $m$ duplicates of $\frac{n}{m}$. If $A \leq B$, we can have $C = A$. If $A \not\leq B$, we must have ...

3

The non-constructive version of Pataraia's theorem is called the Bourbaki-Witt fixed point theorem. I learned it from Davey and Priestley's Introduction to Lattices and Order, and Wikipedia gives the following references: Nicolas Bourbaki (1949). "Sur le théorème de Zorn". Archiv der Mathematik. 2: 434–437. doi:10.1007/bf02036949. Ernst Witt (1951). "...

3

Let suppose $d\le \log n$. We can define a DAG $D$ on $2^d$ vertices $v_1,\ldots,v_{2^d}$, we add edge from $v_i$ to $v_j$ in $D$ if the following conditions hold: bit representation of $i$ is smaller than bit representation of $j$ (w.r.t. the definition of $\le$ in the question), and bit representation of $j$ has exactly one additional $1$ compare to $i$. ...

3

I'd say no. Consider the following example. Let $(A,\land)$ and $(B,\land)$ be two unrelated semilattices. Let $(S,\land)$ be their direct product, and put $(a,b)\le_1(a',b')$ iff $a\le a'$, $(a,b)\le_2(a',b')$ iff $b\le b'$. Then your conditions are satisfied, even though the two preorders look nothing like each other.

3

Graph isomorphism for bipartite graphs is as hard as graph isomorphism for general undirected graphs. Considering bipartite posets (i.e., seeing bipartite graphs as Hasse diagrams of posets), you may see that counting the automorphisms of bipartite posets is as hard as counting the automorphisms of general undirected graphs.

2

If randomness is in bounds, one rough idea would be to generate a bunch of "random monotonic signature" functions and use them to approximate the subset relation (a la Bloom filters). Unfortunately, I don't know how to make this into a practical algorithm, but here are some estimates that don't immediately prove the idea impossible. This is very far from a ...

2

You may find it helpful to think of your problem in terms of equalities and strict inequalities. In the case of the constraints being equalities or disequalities there is a simple saturation procedure based on transitivity of equality. Strict inequalities can be represented by directed edges in a graph. You can then compute strongly connected components ...

2

In a recent paper, we propose such a scheme. The scheme is illustated in a specific crowdsourcing application setting, but the idea is fairly simple. We just see the order constraint $\mu(u) \leq \mu(v)$ of each DAG edge $(u, v)$ as a linear inequality constraint, we consider the admissible convex polytope of assignments to these linear inequalities, and we ...

2

Sorry for the brevity, maybe I can come back and expand later. There is work in voting and modeling voters that should be relevant. For example, take a model, i.e. in Mallows model, if A is truly cuter than B, then with probability $p > 0.5$ I rank $A$ ahead of $B$ and otherwise I rank B ahead of A. All rankings are made independently. Then the ...

2

A trivial observation is that if $|S(x)| \le 2$ for all $x$, then this problem is solvable in polynomial time, by reduction to 2SAT. Here's how. Introduce a variable $v_{x,i}$ for each vertex $x$ and each $i$ such that $i \in S(x)$. For each pair $x,y$ of vertices, if there is a path from $x$ to $y$, we get some constraints: if $i\in S(x)$, $j\in S(y)$, ...

2

Note that if you relax the problem by allowing $f$ to be arbitrary (not necessarily bijective), then it becomes polynomial. The algorithm proceeds similarly to topological sorting: you number the vertices one by one, maintaining the set $U$ of unnumbered vertices whose in-neighbors have been numbered. Whenever possible, you choose a vertex $x \in U$ and ...

2

We can reduce it to the following problem: Given a directed graph on vertex set $\{1,2,\dots,n\}$, we want to know if there exists a permutation $T$ such that for each edge $(i,j)$ in the graph, $T[i]<T[j]$. The reduction: add an edge to the graph for each pair $i,j$ where both $P_b[i]$ and $P_b[j]$ exist for some $b \in \{0,1\}$; the orientation of ...

2

Here is a divide-and-conquer algorithm with running time $O(n^{1.585})$, for arbitrary $d$, assuming the values are "random" and uniformly distributed. Let $X^0$ denote the set of $x_i$'s that start with a 0 bit, and $X^1$ the set of $x_i$'s that start with a 1 bit. Similarly define $Y^0$ and $Y^1$ to be the set of $y_i$'s that start with a 0 or 1 bit, ...

2

I show below that the $G$-test problem is NP-hard for some simple but infinite group $G$. The finite case is still open. proof Define the following functions: $f(x) = -x$ and $g_a(x) = x + a$. Then take $G$ to be the group generated by $f$ and $g_a$ with composition as the operation. Note that the elements of $G$ are $\{f \circ g_a | a \in \mathbb{Z} \} \... 1 You may find the following recent reference useful: M. Caceres, M. Cairo, B. Mumey, R. Rizzi, and A. Tomescu. On the parameterized complexity of the Minimum Path Cover problem in DAGs. arXiv preprint arXiv:2007.07575 1 Co-worker here. We haven't solved it yet, but here are a few remarks (in case it gives anyone an idea, because we are stuck). The main thing we have for now is a partial result on so-called crown-free lattices. To show it, for two elements$x,y$of the poset$P$, I say that$x$is covered by$y$if$x\geq y$,$x \neq y\$, and there are no elements in between ...

1

With my coauthor, we have just posted a preprint which studies this problem more generally for regular languages. In the case of finite groups, we claim that the problem is tractable (in NL) in the case where the partial order on the elements consists of a union of chains: see Theorem 6.2. We would conjecture that the problem for general DAGs is also in NL, ...

Only top voted, non community-wiki answers of a minimum length are eligible