Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

Questions tagged [partial-order]

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

Filter by
Sorted by
Tagged with
-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 ...
user avatar
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 (...
user avatar
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., ...
user avatar
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 $...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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$. ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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)$ ...
user avatar
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 \...
user avatar
  • 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'...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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$ ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 [...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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. ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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-...
user avatar
  • 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-...
user avatar
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 ...
user avatar
  • 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 (...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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). ...
user avatar
  • 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 ...
user avatar
  • 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". ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar