On the maximum acyclic subgraph problem under disjunctive constraints

Disjunctively constrained versions of classic problems in graph theory such as shortest paths, minimum spanning trees and maximum matchings were recently studied. In this article we introduce disjunctive constrained versions of the Maximum Acyclic Subgraph problem. Negative disjunctive constraints s...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 2015-02, Vol.115 (2), p.119-124
Main Authors: Mapa, Sílvia Maria Santana, Urrutia, Sebastián
Format: Article
Language:English
Subjects:
Algorithms
Approximation
Approximation algorithms
Computational complexity
Computer science
Constraints
Data processing
Disjunctive constraints
Graph algorithms
Graph theory
Graphs
Matching
Mathematical problems
Maximum acyclic subgraph problem
Polynomials
Shortest-path problems
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Disjunctively constrained versions of classic problems in graph theory such as shortest paths, minimum spanning trees and maximum matchings were recently studied. In this article we introduce disjunctive constrained versions of the Maximum Acyclic Subgraph problem. Negative disjunctive constraints state that a certain pair of edges cannot be contained simultaneously in a feasible solution. Positive disjunctive constraints enforces that at least one arc for the underlying pair is in a feasible solution. It is convenient to represent these disjunctive constraints in terms of an undirected graph, called constraint graph, whose vertices correspond to the arcs of the original graph, and whose edges encode the disjunctive constraints. For the Maximum Acyclic Subgraph problem under Negative Disjunctive Constraints we develop 1/2-approximative algorithms that are polynomial for certain classes of constraint graphs. We also show that determining if a feasible solution exists for an instance of the Maximum Acyclic Subgraph problem under Positive Disjunctive Constraints is an NP-Complete problem. •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.
ISSN:0020-0190
1872-6119
DOI:10.1016/j.ipl.2014.07.013