# Tag Info

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
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,811

### 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 ...
• 9,547

### 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.5k
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

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

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

### 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 ...
• 12.2k
Accepted

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

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