Critical elements in combinatorially closed families of graph classes
Copyright policy )Critical elements in combinatorially closed families of graph classes
Summary: The notions of boundary and minimal hard classes of graphs, united by the term ``critical classes'', are useful tools for analysis of computational complexity of graph problems in the family of hereditary graph classes. In this family, boundary classes are known for several graph problems. In the paper, we consider critical graph classes in the families of strongly hereditary and minor closed graph classes. Prior to our study, there was the only one example of a graph problem for which boundary classes were completely described in the family of strongly hereditary classes. Moreover, no boundary classes were known for any graph problem in the family of minor closed classes. In this article, we present several complete descriptions of boundary classes for these two families and some classical graph problems. For the problem of 2-additive approximation of graph bandwidth, we find a boundary class in the family of minor closed classes. Critical classes are not known for this problem in the other two families of graph classes.
- N. I. Lobachevsky State University of Nizhny Novgorod Russian Federation
- National Research University Higher School of Economics Russian Federation
computational complexity, hereditary class, efficient algorithm, critical class, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Structural characterization of families of graphs
computational complexity, hereditary class, efficient algorithm, critical class, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), Structural characterization of families of graphs
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).3 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!