# Algorithms Research

Overview

At Vanderbilt, research on algorithms primarily deals with graph algorithms, and issues arising from the study of graph algorithms. A particular area of specialization is recognition algorithms for special classes of graphs. Many graph classes have been constructed in the literature, some because the graph class has been used to model specific problems, and others simply because of nice theoretical properties of the class itself. This research has lead to the development of the fastest known algorithms for recognizing such graph classes as comparability graphs, circular-arc graphs, circle graphs, permutation graphs, weakly chordal graphs, probe-interval graphs, and trapezoid graphs.

Topics

• Robust Algorithms: There is a surprising ambiguity in what it means to say that you have "solved" a problem on a particular class of inputs, which arises particularly if there is no polynomial algorithm to determine whether an input is in the class. We introduce the notion of a robust algorithm for solving an input in a restricted domain; such an algorithm may either solve the problem correctly (whether or not the input is in the domain) or answer that the input is not in the domain. This leads to new definitions of intractability for a domain, as well. There are a large number of open problems, both dealing with specific problems and domains and on more general issues involving proving intractability. J. Spinrad and V. Raghavan.
• Graph Representations: This research deals with questions about how a class of graphs can be represented in a computer. If a graph class is sufficiently small, there are often better ways to represent the class than by general structures such as adjacency matrices and lists. Open problems involve both finding good representations of specific graph classes, and general conjectures regarding representability of all classes of graphs.
• Graph Problems Connected to Matrix Multiplication: This project deals with the time complexity of certain algorithms on graphs. We have been able to reduce the time complexity of a number of well known problems (finding clique cutsets, star cutsets, two-pairs, asteroidal triples, and others) using fast matrix multiplication algorithms as subroutines. We have also given evidence that some of these may truly be tied to matrix multiplication, in that finding efficient algorithms without using matrix multiplication would require a major breakthrough. Open problems involve reducing the time complexity of problems, and providing stronger evidence of the link between these problems and matrix multiplication. Joint work between J. Spinrad and Dieter Kratsch of the University of Metz.
• Probe-Interval Graphs: This research deals with a class of graphs which arise in the context of gene sequencing. We have designed the first polynomial time algorithm to recognize and provide a possible genetic model for these graphs. Current work involves attempts to reduce the time complexity, and to solve a particular generalization of the problem. Joint work between J. Spinrad, Julie Johnson, and Ross McConnell of the University of Colorado at Denver.
• Clique-width: There has been considerable recent interest in a type of graph called bounded clique-width graphs, because many problems which are difficult in general can be solved on graphs with bounded clique-width. In previous papers, solving problems on bounded clique-width graphs required that the input graph was given in a particular form which constituted a proof that the graph had bounded clique-width; thus, the algorithms were not usable on a general graph which happened to have bounded clique-width. We have shown that many of these problems can be solved even if the input is given in standard adjacency matrix form. J. Spinrad, Vijay Raghavan, and Julie Johnson.

Faculty