Questions tagged [partial-order]
A partial order is a binary relation over a set which is reflexive, antisymmetric, and transitive.
48
questions
-2
votes
1answer
54 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
1answer
75 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 (...
7
votes
0answers
87 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., ...
6
votes
2answers
362 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 $...
1
vote
1answer
86 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
1answer
100 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 ...
5
votes
1answer
136 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 ...
10
votes
1answer
283 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
votes
1answer
171 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 ...
7
votes
1answer
368 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
74 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)$ ...
3
votes
3answers
389 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 \...
11
votes
1answer
373 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'...
5
votes
0answers
188 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 ...
12
votes
2answers
871 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 ...
2
votes
1answer
45 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
149 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
270 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
96 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 ...
10
votes
0answers
127 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
300 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
105 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
106 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
157 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
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 ...
6
votes
1answer
335 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
215 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
978 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
886 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
380 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 ...
5
votes
1answer
717 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
410 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
189 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
379 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
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 ...
30
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
251 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
825 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
597 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
596 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
2answers
500 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
482 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
466 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
275 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
382 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 ...
28
votes
0answers
663 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
587 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 ...
46
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 ...
