Second, an inclusion hierarchy is delineated among all of the classes of graphs for which polynomial time feedback vertex set algorithms presently exist. The results presented here serve to unify and focus the work on locating minimum feedback vertex sets in polynomial time. Given a set of intervals on the real line, an interlocking set is a subset of the intervals in which every two intervals are related in the symmetric-transitive closure of the interlock relation. The determination of interlocking sets has application in single-row routing of VLSI systems. In such a coloring, two intersecting intervals must receive distinct colors.
Previous methods are linear only in n, and assume that k is a fixed constant.
Since in most applications, k is substantially smaller than n, the saving is significant. The problem of distance-2 colorings of the vertices of undirected graphs is studied. In such a coloring, vertices separated by a distance not exceeding two must receive different colors. The main result is to show that even when restricted to planar graphs, finding a minimum such coloring is NP-complete. This analysis is extended to deal with general graphs, where it is shown that the performance of the algorithm has a worst-case bound that is proportional to the product of the graph arboricity and the maximum vertex degree.