The max quasi-independent set problem

N. Bourgeois (), A. Giannakos (), G. Lucarelli (), I. Milis (), V. T. Paschos () and O. Pottié ()
Additional contact information
N. Bourgeois: CNRS FRE 3234 and Université Paris-Dauphine
A. Giannakos: CNRS FRE 3234 and Université Paris-Dauphine
G. Lucarelli: CNRS FRE 3234 and Université Paris-Dauphine
I. Milis: Athens University of Economics and Business
V. T. Paschos: CNRS FRE 3234 and Université Paris-Dauphine
O. Pottié: CNRS FRE 3234 and Université Paris-Dauphine

Journal of Combinatorial Optimization, 2012, vol. 23, issue 1, No 8, 94-117

Abstract: Abstract In this paper, we deal with the problem of finding quasi-independent sets in graphs. This problem is formally defined in three versions, which are shown to be polynomially equivalent. The one that looks most general, namely, f-max quasi-independent set, consists of, given a graph and a non-decreasing function f, finding a maximum size subset Q of the vertices of the graph, such that the number of edges in the induced subgraph is less than or equal to f(|Q|). For this problem, we show an exact solution method that runs within time $O^{*}(2^{\frac{d-27/23}{d+1}n})$ on graphs of average degree bounded by d. For the most specifically defined γ-max quasi-independent set and k-max quasi-independent set problems, several results on complexity and approximation are shown, and greedy algorithms are proposed, analyzed and tested.

Keywords: Quasi independent set; Exact algorithms; Approximation algorithms (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-010-9343-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:23:y:2012:i:1:d:10.1007_s10878-010-9343-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-010-9343-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().