6

Graph isomorphism is GI-complete for DAGs: https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Complexity_class_GI. The problem for partial orders is also GI-complete: We can reduce bipartite graph isomorphism (which is GI-complete) to 2 instances of DAG isomorphism where the DAG equals its transitive closure by considering two canonical ways to turn a ...


3

This problem is Feedback Vertex Set in disguise, and hence NP-Hard, but I'd imagine there are good heuristics out there (I don't know the references myself, maybe someone can help me out here). More specifically, for an input graph $G = (V, E)$ with minimal FVS $S \subseteq V$, there is a solution to your problem that copies each member of $S$ once (and no ...


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 ...


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