On the maximum acyclic subgraph problem under disjunctive constraints
A new version of a classic problem in graph theory was introduced. We studied Maximum Acyclic Subgraph under Negative Disjunctive Constrains (MASNDC). We studied Maximum Acyclic Subgraph under Positive Disjunctive Constrains (MASPDC). Six 1/2-approximative algorithms for the MASNDC were developed. We showed that determining the feasibility of MASPDC is NP-Complete.
maximum acyclic subgraph problem disjunctive constraints approximation algorithms computational complexity