# Tag Info

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

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

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

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

4

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.

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

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

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$. ...

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

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

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} \} \... 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 It is NP-hard. The reduction is from$CLIQUE$, so suppose we are given an undirected graph$H$on$n$vertices and$m$edges, with a parameter$k$, and our task is to decide whether$\omega(H)\ge k$. We will need some sufficiently large numbers$M\gg N \gg n$, where we need about$N=n^2$and$M=n^3$. The graph$G$will have two disjoint parts. The first part ... 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, ...

1

Here is a link, may be it can help you. http://fc.isima.fr/~nourine/publications.php M. Habib and L. Nourine : A Linear Time Algorithm to Recognize Distributive Lattices, RR LIRMM, No 92-012, 1992.

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