Graph Problems with Obligations

In this paper we study variants of well-known graph problems: vertex cover, connected vertex cover, dominating set, total dominating set, independent dominating set, spanning tree, connected minimum weighted spanning graph, matching and hamiltonian path. Given a graph (G=(V,E)), we add a partition (varPi _{V}) (resp. (varPi _{E})) of its vertices (resp. of its edges). Now, any solution S containing an element (vertex or edge) of a part of this partition must also contain all the others ones. In other words, elements can only be added set by set, instead of one by one as in the classical situation (corresponding to obligations that are singletons). A motivation is to give a general framework and to study the complexity of combinatorial problems coming from systems where elements are interdependent. We propose hardness and approximation results.