The papers described in this section all deal with one or another graph theoretic problem: Three of the papers deal with feedback vertex sets; three others deal with sets of intervals on the real line: two with coloring and one on locating interlocking sets; and one paper considers two-away colorings of graphs.
The problem of finding a minimum cardinality feedback vertex set of a directed graph is considered. Of the classic NP-complete problem, this is one of the least understood. Although Karp showed the general problem to be NP- complete, a linear algorithm for its solution on reducible flow graphs was given by Shamir. The class of reducible flow graphs is the only nontrivial class of graphs for which a polynomial time algorithm to solve this problem is known. The main result of this paper is to present a new class of graphs - the cyclically reducible graphs - for which minimum feedback vertex sets can be found in polynomial time. This class is not restricted to flow graphs, and most small graphs (10 or fewer nodes) fall into this class. The identification of this class is particularly important since there do not exist good approximation algorithms for this problem. Along with the class, and a simple polynomial time algorithm for finding minimum feedback vertex sets of graphs in the class, several related results are presented. It is shown that there is no forbidden subgraph characterization of the class, and that there is no particular inclusion relationship between this class and the reducible flow graphs. In addition, it is shown that a class of graphs that is related to the reducible flow graphs, is contained in the cyclically reducible class.
This paper also studies the problem of locating minimum feedback vertex sets in directed graphs. First, three new transformation-based classes of graphs for which minimum feedback vertex sets can be computed in polynomial time are introduced. Second, an inclusion hierarchy is delineated among all of the classes of graphs for which polynomial time feedback vertex set algorithms presently exist. Among the classes of graphs included in the hierarchy are: the reducible flow graphs, the cyclically reducible graphs, the three transformation-based classes introduced here, and an infinite sequence of classes based on an algorithm of Smith and Walford for finding minimum feedback vertex sets in arbitrary graphs. It follows from these results that one of the new classes introduced here, as well as each "Smith/Walford" class, properly includes both the reducible flow graphs and the cyclically reducible graphs. The results presented here serve to unify and focus the work on locating minimum feedback vertex sets in polynomial time.
Two intervals on the real line, [i,j] and [k,m] interlock if either i < k < j < m or k < i < m < j. 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. In this paper an algorithm is given for finding all of the interlocking sets of a set of intervals in time O(n alpha(n)), assuming that the endpoints of the intervals are presented in sorted order -- if not, then the running time is O(nlogn). The determination of interlocking sets has application in single-row routing of VLSI systems.
The problem of coloring a set of n intervals (from the real line) with a set of k colors is studied. In such a coloring, two intersecting intervals must receive distinct colors. The main result of this paper is an O(k + n) algorithm for k- coloring a maximum cardinality subset of the intervals. Previous methods are linear only in n, and assume that k is a fixed constant. In addition to the main result, this paper provides an O(kS(n)) algorithm for k-coloring a set of weighted intervals of maximum total weight. Here, S(n) is the running time of any algorithm for finding shortest paths in graphs with O(n) edges. The best previous algorithm for this problem required time O(nS(n)). Since in most applications, k is substantially smaller than n, the saving is significant. An online version of this paper may be found on the web at: http://www.usafa.af.mil/dfcs/papers/mcc/color.html
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. In addition, a good (constant times optimal) approximation algorithm for the distance-2 coloring of planar graphs is described. 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. Previous algorithms could only guarantee a bound proportional to the square of the maximum degree. This problem has some application to broadcast scheduling in multihop radio networks.
The problem of maintaining an approximate solution for vertex cover when edges may be inserted and deleted dynamically is studied in this paper. In particular, a fully dynamic algorithm A1 that, in an amortized fashion, efficiently accommodates such changes, is given. This algorithm utilizes a technique (introduced here) for handling the processing of operations (Inserts and Deletes of edges) in stages consisting of a certain predetermined number of such operations. Within each stage, each operation is executed in the same style. The style may be either Clean or Dirty, depending upon the density of the graph at the beginning of the stage. Further, a generalization of this method is provided that leads to a family of algorithms Ak, k>=1. The amortized running time of each Ak is O(min(v,e^c(k))) per Insert/Delete operation, where c(k) = (1 + sqrt(1+4(k+1)(2k+3)))/(4k+6)) and e denotes the number of edges of the graph G at the time that the operation is initiated. It follows that the second term of this amortized running time may be made arbitrarily close to O(e^sqrt(2)/2). Each of the algorithms given here is 2-competitive, thereby matching the competitive ratio of the best existing off-line approximation algorithms for vertex cover.
This work clarifies certain results on identifying classes of graphs for which minimum feedback vertex sets may be found in polynomial time. Specifically, it establishs that edge-disjoint reducible graphs are a proper subset of forward reducible graphs. It follows from this result that minimum feedback vertex sets from edge-disjoint reducuble graphs can be found in time O(e log v) rather than O(ev^2).