9
votes
Accepted
Computing topological sort while keeping edges "short"
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 ...
- 5,772
8
votes
Accepted
Is the isomorphism problem between posets represented by DAGs GI-complete?
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 ...
- 1,767
7
votes
Generalization of Dilworth's theorem for labeled DAGs
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 ...
- 8,916
7
votes
Pairwise comparison of bit vectors
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$? ...
- 27.3k
4
votes
Accepted
Meet of integer partitions
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 ...
- 551
4
votes
The originator of the fixed point theorem for DCPOs
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 ...
- 32.4k
3
votes
Accepted
Two preorders with same glb
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)\...
- 16.9k
3
votes
Pairwise comparison of bit vectors
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 ...
- 3,440
2
votes
Pairwise comparison of bit vectors
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 ...
- 11.7k
2
votes
Accepted
Generalizing linear interpolation to posets
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(...
- 8,916
2
votes
Accepted
find the most similar topological ordering of a dag
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$. ...
- 13.9k
1
vote
Accepted
Time complexity of finding chain decomposition of partially ordered set
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 ...
- 131
1
vote
Lighting up all elements of a poset by toggling upsets
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-...
- 1,227
1
vote
Determining what can be achieved by a permutation of elements of a noncommutative group
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 ...
- 8,916
1
vote
Lattice problems
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.
- 11
Only top scored, non community-wiki answers of a minimum length are eligible