Questions tagged [partial-order]
A partial order is a binary relation over a set which is reflexive, antisymmetric, and transitive.
48
questions
-2
votes
1
answer
58
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
1
answer
97
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
7
votes
0
answers
93
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
6
votes
2
answers
396
views
find the most similar topological ordering of a dag
Given a permutation $L$ of the $n$ vertices of the directed acyclic graph $G=(V,E)$.
Question: is it NP-hard to find the topological order of the $G$ that is the most similar to the given permutation $...
- 33
1
vote
1
answer
97
views
How to prove that Supremum preorder coincides with Hoare preorder?
Given a complete lattice $(L, \sqsubseteq)$ and a basis of completely $\sqcup$-irreducibles $B_L \subseteq L$, such that $\forall l \in L$, $l=\sqcup\{b \in B_L\ |\ b \sqsubseteq l\}$.
I mean:
Hoare ...
3
votes
1
answer
105
views
Meet of integer partitions
An integer partition of $n$, $A$, is a multiset of positive integers such that $\sum_{a \in A} a= n$. We say that $B \leq A$, if there exists a map $\phi: |B| \to |A|$, such that for $a \in A$, we ...
- 497
5
votes
1
answer
157
views
Is the isomorphism problem between posets represented by DAGs GI-complete?
Given two directed acyclic graphs, how hard is the problem of checking whether the partial orders they represent are isomorphic? Is this problem GI-complete?
I believe this problem is equivalent to ...
- 201
10
votes
1
answer
317
views
Lighting up all elements of a poset by toggling upsets
I consider the following game on a finite poset $(P, <)$. At each point of the game, I have a set of elements $S$ of the poset which are "on", and all others are "off". Initially $S = \emptyset$. ...
- 7,350
7
votes
1
answer
218
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 ...
user49915
7
votes
1
answer
404
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 ...
- 73
5
votes
0
answers
79
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)$ ...
- 815
3
votes
3
answers
429
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 \...
- 10.3k
11
votes
1
answer
405
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'...
- 7,350
5
votes
0
answers
207
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
12
votes
2
answers
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 ...
- 7,350
2
votes
1
answer
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$ ...
- 235
12
votes
0
answers
158
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, ...
- 7,350
11
votes
2
answers
274
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 ...
- 7,350
2
votes
0
answers
103
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 ...
- 235
10
votes
0
answers
129
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,350
7
votes
1
answer
364
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 ...
- 7,350
4
votes
0
answers
117
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
0
answers
114
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 [...
- 1,292
4
votes
1
answer
161
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 ...
- 223
10
votes
1
answer
5k
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 ...
- 7,350
6
votes
1
answer
339
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 ...
- 61
1
vote
1
answer
222
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 ...
- 113
15
votes
3
answers
1k
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 ...
- 7,350
20
votes
1
answer
917
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 ...
- 1,319
2
votes
1
answer
425
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 ...
user15617
5
votes
1
answer
813
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.
...
- 1,521
15
votes
4
answers
423
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 ...
- 7,350
5
votes
1
answer
197
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 ...
- 7,350
12
votes
1
answer
408
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 ...
- 7,350
1
vote
0
answers
103
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 ...
- 111
30
votes
5
answers
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 ...
- 8,641
4
votes
2
answers
254
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-...
- 4,256
7
votes
1
answer
868
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
1
answer
623
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,423
13
votes
1
answer
612
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,073
10
votes
2
answers
517
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 ...
- 902
6
votes
1
answer
508
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 ...
- 189
1
vote
0
answers
470
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
...
- 223
5
votes
2
answers
287
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
3
votes
1
answer
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 ...
- 339
30
votes
0
answers
739
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
12
votes
1
answer
594
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.8k
46
votes
5
answers
3k
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 ...
- 50.2k