Algoritmos para o problema do subgrafo acíclico máximo sob restrições disjuntivas

Abstract

In this work we tackle the Maximum Acyclic Subgraph problem under Negative Disjunctive Constraints (MASNDC) and the Maximum Acyclic Subgraph problem under Positive Disjunctive Constraints (MASPDC), both belonging to the NPHard class. Disjunctive constraints can be negative, in which a certain pair of entities cannot be contained simultaneously in a feasible solution; or positive in that, given a pair of entities, at least one of them must compose a feasible solution. Instances of MASNDC and MASPDC are composed by a directed graph G = (V;A) and a undirected graph G = (A;E), which encodes the disjunctive positive or negative constraints over pairs of arcs of graph G. MASNDC consists in determining a maximum subset A0 A for which the subgraph G0 = (V;A0) is cycle free and A0 is a set of vertices in G such that there are no edges between two of its vertices, namely an independent set at G. MASPDC consists in determining a maximum subset A0 A for which the subgraph G0 = (V;A0) is cycle free and A0 is a set of vertices in G such that every edge in E is incident on some vertex in A0, namely a vertex cover in G. It is proved that the feasibility decision version of MASPDC is NPComplete by a reduction from the classic Vertex Cover problem. For MASNDC we propose six approximation algorithms with constant factor equal to 1=2 for special classes of graph G in which the maximum independent set is polynomial. Among the six algorithms, three of them following the so-called late approach generate solutions with at least the same cardinality of the ones obtained by equivalent algorithms, according to the early approach. We propose a preprocessing of MASPDC and MASNDC instances. Computational experiments on integer linear programming models of both problems suggest that, when performing the preprocessing, solutions of larger cardinalities are obtained, in the same run time. We also proposed an improvement procedure on an heuristically obtained initial solution of MASNDC, which is then linked to a metaheuristic as a local search method. Computational results show that for instances with jV j > 200, the heuristic is preferable to solving the integer programming model by using a commercial software.