Hereditary classes of graphs, hypergraphs, and Boolean functions

We consider hereditary systems of graphs, hypergraphs, Boolean functions, etc. We develop methods for characterizing hereditary classes in terms of forbidden subobjects. Although our results are theoretical, they also have important algorithmic consequences for recognizing hereditary classes and for solving some NP-complete problems.; In Chapter 1, we show that all classes of r-bounded k-complete bipartite bihypergraphs can be characterized by a finite number of forbidden induced subhypergraphs [within bipartite bihypergraphs], implying a polynomial-time recognition algorithm. We provide a forbidden induced subsystem characterization of matroids within all independence systems. We characterize Post classes of Boolean functions in terms of forbidden subfunctions that allows to give a short proof of the classical Post's theorem. Finally, we consider a well quasi-order on graphical sequences.; Chapter 2 contains a general approach, the Reducing Pseudopath Method, to characterize the substitutional closure of all hereditary classes of graphs. The method has important algorithmic consequences for the Weighted Stable Set Problem, the Dominating Set Problem, characterization of new classes of perfect graphs, etc.; In Chapter 3, we consider the Stable Set Problem on hereditary classes of graphs. We provide new methods for extending hereditary classes to obtain wider alpha-polynomial hereditary classes. We construct a new hereditary system of co-stable subgraphs to characterize the class of all (weighted) well-covered graphs.; Chapter 4 is devoted to domination in graphs. We solve well-known open problems related to domination perfect graphs. We characterize locally (independent) well-dominated graphs and construct a hierarchy of classes where the (Independent) Dominating Set Problem can be solved in polynomial time. By introducing so-called satgraphs, we establish a "bridge" between the Satisfiability Problem and the Independent Domination Problem. As a result, we obtain a series of new results concerning the both problems. Also, we characterize some hereditary classes, where the Dominating Set Problem can be solved in polynomial time.