Skip to main content
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 ...
Gamow's user avatar
  • 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 ...
Laakeri's user avatar
  • 1,811
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 ...
a3nm's user avatar
  • 9,547
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$? ...
Ryan Williams's user avatar
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 ...
Antti Röyskö's user avatar
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 ...
Neel Krishnaswami's user avatar
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 ...
Saeed's user avatar
  • 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 ...
D.W.'s user avatar
  • 12.2k
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(...
a3nm's user avatar
  • 9,547
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$. ...
domotorp's user avatar
  • 14k
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 ...
Gabriel Istrate's user avatar
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-...
M.Monet's user avatar
  • 1,429
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 ...
a3nm's user avatar
  • 9,547
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.
user53561's user avatar

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