Originators: Chen Li, David Hannasch (presented by David Hannasch - REGS 2011)
Definitions: Every acyclic digraph $D$ specifies a partially ordered set $P$ whose comparability digraph is the transitive closure of $D$. The linear extensions of $P$ are sometimes called topological orderings of $D$; we simply call them linear extensions.
Background: We are trying to construct a timeline on a set of events. Reader robots read some text and provide us with tentative information on the ordering of events. They produce an oriented graph. We want to extend it to a linear ordering (a transitive tournament). Unfortunately, the oriented graph may contain cycles. (Robots make mistakes, and the original text may itself be in error; we might be dealing with Twitter feeds, after all.)
If adding an edge to an acyclic digraph creates a cycle, then adding its reversal does not. Thus reversing and removing an edge in a cycle are essentially equivalent, and every acyclic oriented graph $D$ extends to a transitive tournament, which corresponds to a linear extension (timeline) of $D$. To correct the robots' mistakes, we have an optimization problem.
Maximum Acyclic Subdigraph: Given an oriented graph $D$, make it acyclic by reversing the fewest edges. Equivalently, find an acyclic subdigraph with the most edges.
Hassin and Rubinstein [HR] showed that the weighted version of this problem is NP-hard. They produced an approximation algorithm for the unweighted problem that finds an acyclic subgraph with more than half as many arcs as the optimal one. Guruswami, Monokaran, and Raghavendra [GMR] showed that an approximation ratio strictly larger than 1/2 is UG-hard. However, it may be possible to find better algorithms for classes of graphs. For example, the problem is polynomially solvable on planar graphs [HR]. The number of edges needed to be reversed is always the transversal number of the hypergraph $H$ defined on $E(D)$ such that the edges of $H$ are the edge sets of cycles in $D$.
A motivation for the weighted version is that information may come from several robots with different reliabilities. We then form a single weighted oriented graph by totaling the weights on all the edges, with weights in opposite directions canceling.
There may be many largest acyclic subdigraphs. Can they differ substantially in the number of linear extensions?
Question 1: Among $n$-vertex oriented graphs, what it is the largest possible ratio between the numbers of linear extensions of two maximal acyclic digraphs?
Comments: The number of linear extensions measures, roughly, how much uncertainty we have about a timeline from a given acyclic oriented graph. As such, we might choose not to include in our count of edges those edges which were implied by transitivity. For an input poset (or acyclic digraph), Brightwell and Winkler [BW] showed that counting the linear extensions is #P-complete (they provided an approximation algorithm). Kahn and Kim [KK] gave bounds within a factor that is exponential in the number of elements.
Extremal problems that don't compare acyclic subdigraphs of a single digraph seem easier. In particular, among $n$-vertex digraphs with $m$ edges, we may ask which have the maximum and minimum numbers of linear extensions. When $m\ge n-1$, the digraph consisting of a spanning path plus additional edges in accordance with transitivity has only one linear extension.
Conjecture 2: When $m\lt n-1$, the minimum number of linear extensions is $n_{(n-m-1)}$, achieved by a path of length $m$ plus $n-m+1$ isolated vertices.
Conjecture 3: (Galvin) The maximum number of linear extensions is achieved by taking the first $m$ edges in the lexicographic order $12,.~.~.,1n,23,.~.~.~,2n,34,.~.~.$
Comments: When $m\le n/2$, the number of linear extensions of the digraph consisting of $m$ isolated edges and $n-2m$ isolated vertices is $\frac{(2m)!}{2^m} n_{(n - 2m)}$, which is greater than $n_{(n - m - 1)}$. As an analogue to Conjecture 3, it follows from the Kruskal-Katona Theorem that taking the first $m$ (undirected) edges in lexicographic order maximizes the number of independent sets.
References:
[BW] Brightwell, Graham; Winkler, Peter; Counting linear extensions.
Order 8 (1991), 225-242.
[HR] Hassin, Refael; Rubinstein, Shlomi; Approximations for the maximum acyclic
subgraph problem. Inform. Process. Lett. 51 (1994), no. 3, 133.140.
[KK] Kahn, Jeff; Kim, Jeong Han; Entropy and sorting.
24th Annual ACM Symposium on the Theory of Computing (Victoria, BC, 1992).
J. Comput. System Sci. 51 (1995), 390-399.
[GMR] Guruswami, V.; Manokaran, R.; Raghavendra, P.;
Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic
Subgraph,
49th Annual IEEE Symposium on Foundations of Computer Science (2008), 573-582.