The Maximum Set Problems

Minisymposium: VERTEX COLOURINGS AND FORBIDDEN SUBGRAPHS

Content: The method of augmenting graphs is a general approach to solve the Maximum Independent Set problem. Our objective is to employ this approach to develop polynomial-time algorithms for some so-called Maximum Set problems, i.e. problems which can be stated as follows. Given a (simple, undirected) graph $G$, find a maximum vertex subset $S$ of $G$ such that the subgraph induced by $S$ satisfies a given property $\Pi$. Such problems were shown to be NP-hard in general if the properties considered are non-trivial and hereditary. In this talk, using the augmenting graph technique, we describe a graph class, in which some problems can be solved in polynomial time. We also prove the NP-hardness of some Maximum Set problems where the considered properties are not hereditary.

Back to all abstracts