# Tag Info

12

With multiple copies of the same label allowed, the problem is NP-hard, via a reduction from cliques in graphs. Given a graph $G$ in which you want to find a $k$-clique, make a DAG with a source vertex for each vertex of $G$, a sink vertex for each edge of $G$, and a directed edge $xy$ whenever $x$ is a vertex of $G$ that forms an endpoint of edge $y$. Give ...

9

I think this problem is NP-hard. I try to sketch a reduction from MinSAT. In the MinSAT problem we are given a CNF and our goal is to minimize the number of satisfied clauses. This problem is NP-hard, see e.g., http://epubs.siam.org/doi/abs/10.1137/S0895480191220836?journalCode=sjdmec Divide the vertices into two groups - some will represent literals, the ...

5

Every simplification order is indeed a well-partial order because of this simple statement: If $R$ is a well-quasi order, and $S$ is a partial order, and $R\subseteq S$, then $S$ is a well-partial order. Proof: Exercise. Note that this nice property is not true for well-founded orders in general! In this sense, well-quasi orders are much more "stable". ...

4

Surely, you want $s_1 < s_2$ if there is a $t$ such that $s_1.t < s_2.t$ and $s_1.u \leq s_2.u$ for every other field $u$. That, at least, gives you a well-founded order. But there are many other well-founded orders on tuples, e.g. lexicographical order for some order of the fields (though you might need a heuristic to find the order), and various ...

3

Here's a nice property of WQOs: If $R$ is a WQO on terms, and $S$ is another transitive relation such that $$R\ \subseteq\ S$$ Then $S$ is a WQO Proof: Let $t_1,\ldots, t_n,\ldots$ be an infinite sequence of terms. Because $R$ is a WQO, there are $i, j$ with $i<j$ such that $t_i\ R\ t_j$. But this implies $t_i\ S\ t_j$, so $S$ is a WQO as well. ...

3

I'd say no. Consider the following example. Let $(A,\land)$ and $(B,\land)$ be two unrelated semilattices. Let $(S,\land)$ be their direct product, and put $(a,b)\le_1(a',b')$ iff $a\le a'$, $(a,b)\le_2(a',b')$ iff $b\le b'$. Then your conditions are satisfied, even though the two preorders look nothing like each other.

2

According to this reference (1), the lexicographically first topological order problem is NLOG-complete. You may want to take a more thorough look at the article to ensure that it covers the case(s) that you're interested in. In particular, based on the technical report version (pdf) of that article, it appears that they're treating the lexicographic ...

2

A trivial observation is that if $|S(x)| \le 2$ for all $x$, then this problem is solvable in polynomial time, by reduction to 2SAT. Here's how. Introduce a variable $v_{x,i}$ for each vertex $x$ and each $i$ such that $i \in S(x)$. For each pair $x,y$ of vertices, if there is a path from $x$ to $y$, we get some constraints: if $i\in S(x)$, $j\in S(y)$, ...

2

Note that if you relax the problem by allowing $f$ to be arbitrary (not necessarily bijective), then it becomes polynomial. The algorithm proceeds similarly to topological sorting: you number the vertices one by one, maintaining the set $U$ of unnumbered vertices whose in-neighbors have been numbered. Whenever possible, you choose a vertex $x \in U$ and ...

2

I show below that the $G$-test problem is NP-hard for some simple but infinite group $G$. The finite case is still open. proof Define the following functions: $f(x) = -x$ and $g_a(x) = x + a$. Then take $G$ to be the group generated by $f$ and $g_a$ with composition as the operation. Note that the elements of $G$ are $\{f \circ g_a | a \in \mathbb{Z} \} \... 1 Co-worker here. We haven't solved it yet, but here are a few remarks (in case it gives anyone an idea, because we are stuck). The main thing we have for now is a partial result on so-called crown-free lattices. To show it, for two elements$x,y$of the poset$P$, I say that$x$is covered by$y$if$x\geq y$,$x \neq y\$, and there are no elements in between ...

1

With my coauthor, we have just posted a preprint which studies this problem more generally for regular languages. In the case of finite groups, we claim that the problem is tractable (in NL) in the case where the partial order on the elements consists of a union of chains: see Theorem 6.2. We would conjecture that the problem for general DAGs is also in NL, ...

1

Here is a link, may be it can help you. http://fc.isima.fr/~nourine/publications.php M. Habib and L. Nourine : A Linear Time Algorithm to Recognize Distributive Lattices, RR LIRMM, No 92-012, 1992.

Only top voted, non community-wiki answers of a minimum length are eligible