Edge Maximal Acyclic Subgraph (EMAS)

Input

A directed graph $G = (V, E)$ with an ordering on the edges and a designated edge $e$.

Problem

Is $e$ contained in the edge maximal acyclic subgraph?

Definitions

The edge maximal acyclic subgraph is defined to be the subgraph computed by an algorithm that builds up the acyclic subgraph by processing edges in order. It adds an edge to the subgraph if its inclusion does not introduce a cycle.

Status

$\P$-complete (Greenlaw [1]).

Remarks

The reduction to show hardness is from NORCVP. The decision problem “Is the edge maximal subgraph of size $k$?” is also $\P$-complete [1]. The Feedback Arc Set Problem (Karp [2]) is an equivalent formulation of the Maximum Acyclic Subgraph Problem. Approximation algorithms for this problem are important because there are very few classes of graphs for which the problem is known to be in $\P$ (Berger and Shor [3]). These versions are both $\NP$-complete (Garey and Johnson [4]).

Greenlaw proves decision problems based on several other natural approximation algorithms for this problem are $\P$-complete [1][5]. There are other reasonable approximation algorithms that are in $\NC$, see [1][5]. Berger presented an $\NC$ approximation algorithm that, assuming the input graph does not contain two-cycles, generates a subgraph containing more than half the arcs [6]. Ramachandran proved that finding a minimum weight feedback arc set in a reducible flow graph with arbitrary weights on the arcs is $\P$-complete [7][8].