Questions tagged [partial-order]
A partial order is a binary relation over a set which is reflexive, antisymmetric, and transitive.
7
votes
1answer
94 views
The originator of the fixed point theorem for DCPOs
Pataraia proved in
"A constructive proof of Tarski’s fixed-point theorem for dcpo's", presented in the 65th Peripatetic Seminar on Sheaves and Logic, in Aarhus, Denmark, November 1997
that in a ...
6
votes
1answer
222 views
Computing topological sort while keeping edges “short”
Motivation: I want to compute a topological sort order in which the connected vertices are close to each other.
Problem statement: Given a DAG $G(V,E)$ with $n$ vertices, compute a topological sort ...
5
votes
0answers
63 views
Series-parallel extension of a partial order respecting a given total order
Consider a partial order $P$, a series-parallel order $Q$ and a total order $R$, such that $P \subseteq Q \subseteq R$. Given $P$ and $R$, we are asked to find $Q$ of minimum length.
An $O(n^3)$ ...
4
votes
3answers
289 views
Pairwise comparison of bit vectors
Define a partial order $\le$ on $\{0,1\}^d$ by pointwise comparison, i.e., we say $x \le y$ if $x_i \le y_i$ for all $i=1,2,\dots,d$.
I am interested in the following problem:
Given $x_1,\dots,x_n \...
12
votes
1answer
273 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'...
4
votes
0answers
161 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 ...
11
votes
1answer
571 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 ...
3
votes
1answer
41 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$ ...
12
votes
0answers
118 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, ...
11
votes
2answers
229 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 ...
2
votes
0answers
82 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 ...
9
votes
0answers
114 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 ...
7
votes
1answer
258 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 ...
4
votes
0answers
100 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
vote
0answers
90 views
Is there a useful notion of pathwidth-treewidth for posets?
Consider a poset $P = (V,A)$. We may define a path structuring of $P$ as a chain $\Sigma$ of the form $X_0 \subset X_1 \subset \ldots \subset X_n$ where :
(i) for every $x \in V$, the set $\{ i \in [...
4
votes
1answer
139 views
Compatible partial permutations
Please, correct my terminology as I am not a combinatorician
(I am using http://en.wikipedia.org/wiki/Partial_permutation). Please, refer me to the solution if this is a solved problem.
Let $P_k$ be ...
10
votes
1answer
2k views
Monotone bijections between lists of intervals
I have the following problem:
Input: two sets of intervals $S$ and $T$ (all endpoints are integers).
Query: is there a monotone bijection $f:S \to T$?
The bijection is monotone w.r.t. the set ...
6
votes
1answer
321 views
Linear ordering from weighted directed graph (kittens)
I want to build a website to find the cutest kitten(TM) there is. People can upload photos of their kittens, but also can vote on which kitten is the cutest. However, I don't want them to rate on a 1 ...
1
vote
1answer
199 views
How to find the set of edges for the directed graph associated with a partial order?
I have a set $S$, and a partial order relation $\preceq$ defined on $S$. The way this partial order is given to me is through a function $f:S\times S \to \{true, false\}$, where $f(a,b) = true$ if ...
15
votes
3answers
859 views
Complexity of topological sort with constrained positions
I am given as input a DAG $G$ of $n$ vertices where each vertex $x$ is additionally labeled with some $S(x) \subseteq \{1, \ldots, n\}$.
A topological sort of $G$ is a bijection $f$ from the vertices ...
20
votes
1answer
813 views
How fast can we compute the set inclusion poset of a set family?
Given a set family $\mathcal{F}$ of subsets of a universe $U$.
Let $S_1,S_2 \in \mathcal F$ and we want to answer is $S_1 \subseteq S_2$.
I am looking for a data-structure that will allow me to ...
2
votes
1answer
317 views
Verifying consistency of strict and non-strict partial orders constraints
I am building a set of constraints of the kind $x < y$ and $x \leq y$, where $<$ is a strict order and $\leq$ is a non-strict order on the same set, and $x$ and $y$ are abstract variables ...
4
votes
1answer
545 views
Efficient representation of set of partial order
I guess that notions I describe are already well known, may be by combinatorician, but I do not know their name or any book/article about them. So if you have a link/title I would love to read it.
...
15
votes
4answers
370 views
Worst number of questions needed to learn a monotonic predicate over a poset
Consider $(X, \leq)$ a finite poset over $n$ items, and $P$ an unknown monotonic predicate over $X$ (i.e., for any $x$, $y \in X$, if $P(x)$ and $x \leq y$ then $P(y)$). I can evaluate $P$ by ...
5
votes
1answer
186 views
Generalizing linear interpolation to posets
Assume that I have an array $A$ of $n$ numerical values where some are known and some are unknown (with $A[0]$ and $A[n-1]$ assumed to be known). If I want to estimate an unknown value $A[i]$, a ...
12
votes
1answer
325 views
Minimal elements of a monotonic predicate over the powerset $2^{|n|}$
Consider a monotonic predicate $P$ over the powerset $2^{|n|}$ (ordered by inclusion). By "monotonic" I mean: $\forall x, y \in 2^{|n|}$ such that $x \subset y$, if $P(x)$ then $P(y)$. I am looking ...
1
vote
0answers
100 views
What effect would using different types of orders have on a binary search tree?
Recently, I was coding a comparator function for use in a set backed by a binary search tree, and the set kept saying that it didn't contain elements that I had previously added to it. I eventually ...
27
votes
5answers
3k views
Binary search generalizations for posets?
Suppose I have a poset "S" and a monotonic predicate "P" on S.
I want to find one or all maximal elements of S satisfying P.
EDIT: I'm interested in minimizing the number of evaluations of P.
What ...
4
votes
2answers
239 views
Number of subsets on a set with partial order
Given a set $S$ with strict partial order $<$. Let $A\subseteq S$ be a downward-closed subset of $S$ (in other words, if $a<b$ and $b\in A$, then $a\in A$). How many subsets of $S$ are downward-...
7
votes
1answer
767 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-...
3
votes
1answer
559 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 ...
13
votes
1answer
499 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 (...
10
votes
1answer
383 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 ...
6
votes
1answer
365 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
0answers
444 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
...
5
votes
2answers
246 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). ...
3
votes
1answer
377 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 ...
27
votes
0answers
612 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".
...
12
votes
1answer
558 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 ...
45
votes
5answers
2k views
Positive topological ordering
Suppose I have a directed acyclic graph with real-number weights on its vertices. I want to find a topological ordering of the DAG in which, for every prefix of the topological ordering, the sum of ...
