# Questions tagged [partial-order]

A partial order is a binary relation over a set which is reflexive, antisymmetric, and transitive.

49 questions
Filter by
Sorted by
Tagged with
52 views

### hardness of partition of permutation into a minimum number of monotone subsequences

Given a permutation P, a monotone subsequence is a subsequence (i.e. the elements do not have to be consecutive in P) that increases or decreases. This leads naturally to the following optimization ...
65 views

### Finding a greedy ordering criteria

I've been thinking through a problem, and I won't go into all the details here but I'm stumped on a particular subproblem: Consider this following definition of a task: $T_k = (a_k, b_k)$. $a_k$ is ...
1 vote
130 views

### Time complexity of finding chain decomposition of partially ordered set

Given a partially ordered set $P$ with $n=|P|$ and width $w$: -What is the best known complexity (in expectation) for finding a chain decomposition of $w$ chains? -What is the best known complexity (...
• 23
96 views

### Jump number approximation algorithm

A linear extension $x_1 x_2 \ldots x_n$ of a partially ordered set (poset) is said to have $k$ jumps if there are $k$ occurrences of consecutive elements that are incomparable with each other -- i.e., ...
• 342
411 views

• 11.1k
444 views

### Generalization of Dilworth's theorem for labeled DAGs

An antichain in a DAG $(V, E)$ is a subset $A \subseteq V$ of vertices that are pairwise unreachable, namely, there are no $v \neq v' \in A$ such that $v$ is reachable from $v'$ in $E$. From Dilworth'...
• 8,224
229 views

### NP-completeness of a specific topological sorting problem

Consider $(V, E)$ be a DAG, and $p_1, \dots, p_n$ be its topological sorting (i.e. such permutation $p$ of $V$ that $\forall(x, y) \in E.\ p^{-1}(x) < p^{-1}(y)$). Let's call the goodness of $p$ a ...
• 191
1k views

### Enumerating topological sorts of a vertex-labeled DAG

Let $G = (V, E)$ be a directed acyclic graph, and let $\lambda$ be a labeling function mapping each vertex $v \in V$ to a label $\lambda(v)$ in some finite alphabet $L$. Writing $n := |V|$, a ...
• 8,224
48 views

### Two preorders with same glb

I have a set $S$ with two preorders $\mathord{\le}_1,\mathord{\le}_2\subseteq S\times S$ which a priori are unrelated. Let $\equiv_1$ and $\equiv_2$ be the induced equivalences (i.e., $x\equiv_1 y$ ...
165 views

### Is it #P-hard to compute the number of antichains of a distributive lattice?

An antichain of a poset $(P, <)$ is a subset of pairwise incomparable elements, namely, a subset $A \subseteq P$ such that there are no $x, y \in A$ with $x < y$. By a result of Provan and Ball, ...
• 8,224
278 views

### Determining what can be achieved by a permutation of elements of a noncommutative group

Fix a finite group $G$. I am interested in the following decision problem: the input is some elements of $G$ with a partial order on them, and the question is whether there is a permutation of the ...
• 8,224
106 views

### Completeness of the quotient of the power set lattice of a partial order induced by the Hoare pre-order

Let $(P,\le)$ be a partially ordered set and $\preceq$ the Hoare pre-order on its subsets, i.e. for $X,Y\subseteq P$, $X\preceq Y$ iff $\forall x\in X:\exists y\in Y:x\le y$. Let $\sim$ be the ...
132 views

### Reconstructing labeled poset from linear extensions

Let $(P, <, \mu)$ be a labeled poset, that is, a partial order $(P, <)$ with a labeling function $\mu$ that maps the elements of $P$ to labels in an alphabet $\Sigma$. A label list (or word) is ...
• 8,224
380 views

### Complexity of counting poset automorphisms

A (finite) poset $P = (X, <)$, or partially ordered set, is a (finite) set $X$ equipped with a transitive antisymmetric relation $<$; it can be equivalently seen as a DAG $G = (X, E)$ that is ...
• 8,224
121 views

### The rank-polynomial of a graded poset

Let $P$ be a graded poset with rank function $r$. We may then define its rank-polynomial as: $R_P(q) = \sum_{x \in P} q^{r(x)}$. This definition can be applied to several interesting posets, for ...
• 1,292
1 vote
115 views

• 4,327
893 views

### On finding a chain decomposition of a Partial Order

I am reading a paper by Daskalakis et al. entitled "Sorting and Selection in Posets". http://arxiv.org/abs/0707.1532 In that paper it is presented an enhancement to the algorithm Poset-...
639 views

### My exact divide-conquer algorithm for counting antichain in a poset?

This post is a little lengthy, thank your for your patience for reading. ^_^ As known, counting antichains in a poset is #P-complete, so it is NP-hard to get the exact answer. Following is my simple ...
• 1,433
642 views

### Is counting maximal cliques in an incomparability graph #P-complete?

This question is motivated by a MathOverflow question by Peng Zhang. Valiant showed that counting maximal cliques in a general graph is #P-complete, but what if we restrict to incomparability graphs (...
• 7,093
526 views

### Lattice problems

There has been a fair amount of work on computational problems for partial orders (e.g., recognition, jump number, comparability graph recognition, etc...). I am curious what work specific to ...
537 views

### reference for lexicographic path ordering

Can you recommend a good reference for reading about lexicographic/recursive path orderings? I'm currently reading about lpo's in Chapter 2 of the Handbook of Automated Reasoning, 'Resolution Theorem ...
1 vote
472 views

### Well Defined Ordering Relations in Object Oriented Type Systems [closed]

In any Object-Oriented type system the type relation of two objects A and B can be characterized in exactly one of the following ways: A has the same type as B A is a subtype of B B is a subtype of A ...
295 views

### Partially Ordered CFG

I'm looking for work about partially ordered context-free grammars. I've found one paper, which seems to simplify the problem too much (in addition to some technical mistakes, as far as I can tell). ...
• 283
384 views

### Extension of a partial order to a total of partitions of a weak alternating automaton

My problem is this: given a weak alternating automaton and its partitions, and given a partial order on these partitions, how do we extend the partial order to a total order? The partitions of weak ...
• 349
765 views

### The complexity of checking whether two DAG have the same number of topological sorts

This problem is highly related to the CNF one. Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No". ...
• 709
596 views

### Positive topological ordering, take 2

This is a followup to David Eppstein's recent question and is motivated by the same problems. Suppose I have a dag with real-number weights on its vertices. Initially, all of the vertices are ...
• 22.9k