Please mail me with any corrections, or any other comments. The list is very rough at the moment. Bipartite Classes 1) Chordal Bipartite Graphs The fastest known algorithms for recognizing chordal bipartite graphs involve lexically ordering a matrix, and checking for a forbidden configuration. The checking is linear, and the ordering takes O(mlogn) or O(n^2) time. The ordering algorithm is designed for any matrix, whether or not it has the forbidden configuration. Can you use the fact that the matrices are special to design a linear time algorithm? 2) Find a Geometric Model for Chordal Bipartite Graphs (Spinrad) 3) Bipartite graphs with no induced cycle of length > 6 (Spinrad) Count, recognize, find a good representation of them. 4) Perfect Elimination Bipartite Recognition Perfect elimination bipartite graphs are discussed in Golumbic's book, and correctly model perfect Gaussian elimination in arbitrary matrices. However, the best recognition algorithm for these graphs takes O(n^3) time, and actually performing Gaussian elimination can be done in O(n^3) time. These graphs would seem much more useful if they could be recognized in much less time than performing the elimination. 5) Chordal Bipartite Plus weight condition (Shamir) Must find gamma-free ordering in which for all row/column pairs topleft + bottomright <= bottomleft + topright. O(mnlogn) Alon, ?, Hochbaum, Ditrich. Chordal Graphs and Variants 1) Finding Simplicial Vertices (Spinrad) Can you find a simplicial vertex in an arbitrary graph in time less than matrix multiplication? 2) Finding holes in graphs How efficiently can you determine whether a graph has no hole of length > k? The best I can do is O(n^(k-.634)). Can you determine whether a graph has a chordless cycle containing a particular vertex v in linear time? This would allow an O(m^2) algorithm for k = 5. Can you recognize graphs which are "generalized simplicially reducible" efficiently; i.e., graphs which can be reduced to the empty graph by successively removing vertices which are not in the center of a $P sub k$? Is it NP-complete to determine the smallest value $k$ such that $G$ is "$k$-simplicially reducible"? Can you determine whether a pair of vertices is in a common hole of length > 4 in polynomial time? 3) Chi-boundedness of hole-free graphs (Sritharan) Hole free (not antihole-free) graphs, can the chromatic number be hugely different from the size of the maximum clique? ) 4) Extending cycles in chordal graphs (Hendry, XingXing) For a chordal graph G, and a cycle (not induced) of length k < max cycle in G, can you always add a vertex and rearrange to get a cycle of length k+1? Circle Graphs and Variants 1) Polygon in circle graphs (Lubiw) A circle graph is the intersection graph of chords in the circle. What do you get for the intersections of k-gons in the circle? The two most natural subproblems to me here are recognition of triangle in circle, and general kgon- I very much doubt that this gives all graphs, but I have no proof at the moment. Circular-Arc Graphs 1) Certificate that G is not circular-arc (Eschen, Raghavan) Although we have an efficient recognition algorithm, can you give an easy proof to someone that G is not circular-arc? Bouchet has done this for circle graphs, for example. 2) Dimension of "circular-arc interesection orders" (Trotter) Consider a circular-arc graph which is a comparability graph. Qin and Trotter show the dimension is at most 4; can it be as high as 4 or not (it can be 3). Comparability Graphs 1) Transitive graph recognition (Spinrad) Can you recognize transitive graphs in less time than it takes to perform the transitive closure of the graph, or are these problems provably of the same complexity? A fast transitive graph recognition algorithm would improve the time complexity of the best known algorithm for comparability graph recognition. The same problem is interesting for the transitive reduction. 2) Verification of transitivity You can verify the result of a matrix multiplication in O(n^2) time probabilistically. For checking if a graph is transitive, can you make this deterministic? Note: you cannot use the result above to get O(n^2) probabilistic transitive graph recognition; the result does not apply (at least immediately) to Boolean matrix multiplication. 3) Chordal comparability graphs (Ma, Spinrad) Is there a good intersection model for this class? Can we tell in O(n) time whether the transitive closure of a graph is chordal, if we are given the diagram? 4) Intersections, Strings on 1 wall (Sritharan) The intersection graphs of strings on 2 walls is the cocomparability graphs; what do we get if we restrict to one wall? 5) New approaches to Transitive Graph Recognition (Mada, Sri) 5a) Given a transitive graph G, can we compute the transitive reduction of G in O(n^2) time? 5b) Given 2 graphs G1 and G2, can we verify in O(n^2) time that G1 is the transitive reduction of the transitive graph G2? 5c) Can you reduce verification of boolean matrix multiplication to recognition of transitive graphs? Note: transitive verification can be reduced to both transitive reduction verification and matrix verification in O(n^2) time; what of the other possible reductions? 5d) Can you come up with an O(kn^2 + m) transitive closure/reduction algorithm, where k is the number of missing/extra edges in the transitive closure/reduction? 6) Problems when given subset of transitive closure (Spinrad, Mohring) Suppose that you are given a subset of the transitive closure of a partial order (in my algorithms, I have always assumed that you have the transitive closure). Is it possible to perform substitution decomposition without performing a general transitive closure algorithm? This is possible for series-parallel partial orders, for example. There are two separate subproblems of this; in one, you may assume that you have the diagram of the partial order, while in the more general case you have anything which contains the transitive reduction and is contained in the transitive closure. Can you determine whether a partial order is N-free in linear time, if no assumption is made about the "completeness" of the input? Decompositions 1) Clique separator decomposition (Whitesides, Tarjan) Can you improve the time complexity, 1st for primetesting and then for the whole decomposition? I would suggest seeing what is implied by a and b on the same side; perhaps partitioning and pseudoparallelism will work. 2) Generalized join decomposition (Hsu, JCT B 1987) Hsu describes a decomposition, which has an alternative chartacterization as follows: can G be partitioned into X, Y such that the edges between X and Y do not contain an induced 2K2 (edges within X,Y ignored). Can we determine whether G has such a decomposition in polynomial time? Which graphs are "completely decomposable" with respect to the join decomposition, and can they be recognized efficiently; or alternatively, does this notion actually make sense at all (it could depend on the decomposition sequence)? I note that all permutation graphs are completely decomposable with respect to generalized join. 3) Decomposition with forbidden subgraphs (Spinrad) This problem is a generalization of the problem above. Given a fixed bipartite subgraph H, can G be partitioned into X, Y so that the bipartite subgraph of edges between X and Y does not contain H (we might also assume that X and Y are at least as large as the smaller side of the bipartition of H)? Can you characterize the class of graphs H for which this is polynomial (or, is it always polynomial?) 4) Split decomposition We can find the split decomposition of an undirected graph in O(n^2) time. Can you do the same for a directed graph? Should be doable using the same ideas. 5) Ordered Neighborhood Decomposition (Ma) A (separable) chordal graph a separator which is a clique. Having a clique separator allows you to decompose G so that holes and antiholes are preserved. The same could be said if you allow the separator to be a set of vertices whose neighborhood are ordered by set inclusion. Can you find such a separator in polynomial time? What kind of graphs are "completely separable" in this sense? 6) Hole preserving decomposition Can you find algorithms for the following types of decompositions? Partition V into V1, V2 such that every long hole is contained in one of the 2 sets. Partition E into E1, E2 with the same property. Partition V into V1, V2 such that at least one edge is within each side, and any hole of length k has at least k-1 vertices on a single side. Dimension See also the excellent list of problems prepared by Trotter, and my paper on dimension and algorithms from ORDAL. 1) Do Problems become easy if given a Realizer? Can you find a problem which is easy on 3-dimensional partial orders if you are given the three lists which represent the graph? Sometimes, this might be the way the information is given to you. (Obviously, the dimension problem is not an interesting example). I might suggest domination problems. How about transitive closure or reduction? How quickly can you do these in 3d posets with and without the realizer (see ORDAL paper). Same for clique, independent set, independent set/clique of size n^.5, ... 2) Dimension Calculation for Special Classes Find interesting classes of posets for which the dimension is calculable in polynomial time. Some open classes are interval orders, cycle-free orders (note: these have dimension at most 4), W-free, bounded width. For height 1 partial orders, are the 3 dimensional orders recognizable in polynomial time? 3) Dimension of Chordal bipartite graphs (Spinrad) How fast can dimension grow with n? It must grow as fast as clogn; O(logn) would give a good representation for graphs in the class 4) Dimension Completion (Spinrad) This problem came up when I thought about writing a program to try to test the conjecture that a class of partial orders was always 3 dimensional. How would you test 3-dimensionality? The obvious approach is to generate all extensions, and see whether each can be part of a realizer of size 3. The question is, once the first list is fixed, can you determine in polynomial time whether 2 more lists suffice? 5) Constructing a realizer Greedily (Spinrad) If you are trying to construct a realizer, a natural approach is to try to "satisfy" as many pairs as possible with a linear extension; a pair of unrelated elements x,y is satisfied if each comes before the other in some linear extension. Given a set of linear extensions, can you find an extension which satisfies the maximum number of pairs? Given a poset, can you find 2DPO which satisfies maximum number of pairs? 6) Dimension reducing extension (Rival) Is there a way to add one relation at a time so that the dimension never increases on the way to finding a linear extension? 7) Construct poset from realizer (Spinrad) Perhaps the simplest open problem to state here is constructing the poset in linear time from a set of 3 linear extensions; for others see ORDAL paper. 8) Crossing Number (Urrutia) The crossing number is an alternative parameter for measuring partial orders. A partial order on n vertices is represented as a set of n functions, with a > b iff the function corresponding to a is always above the function corresponding to b. For any such representation R, we can count C(R) = the maximum number of times that two functions corresponding to unrelated pairs of vertices cross. The crossing number is the minimum value of C(R) over all representations of R. Can the crossing number be computed in polynomial time (conjectured NP-complete for all k > 1). What is the expected value of the crossing number for an n element poset? 9) Problems on 2 dimensional partial orders Open problems include several variants of scheduling problems (e.g. weighted completion time), optimal linear arrangement, jump number, and counting the number of linear extensions. Many of these are also open for other classes (interval orders, N-free, cycle-free, ...). 10) Dimension Approximation Is there a constant c such that for any partial order of dimension k, you can construct a realizer of size at most ck in polynomial time? This is a famous open problem, but even the following is unknown and must be "easy"; given a 3 dimensional poset, produce a set of O(n^(1-epsilon)) linear extensions which realize the poset. Alternatively, show that dimension approximation requires OMEGA(n^epsilon) times the optimal for some epsilon. Interval and Interval Variants 1) Astroidal Triple-free Graph recognition (Corneil, Stewart, Olariu) Can you recognize them in o(n^3) time? 2) Tolerance Graphs (Golumbic, Monma) In a tolerance graph, each vertex is associated with both an interval and a positive value t called a "tolerance". Two vertices are adjacent if their overlap is greater than the minimum tolerance of the two vertices; this generalizes both the interval graphs (tolerance = 0) and the permutation graphs (tolerance = length of interval). Can you recognize tolerance graphs in polynomial time? 3) Intershold Graphs In this variant of threshhold graphs, you assign weights to vertices so that 2 vertices are adjacent if and only if their sum is within a certain interval (rather than being over some threshhold). Can they be recognized in polynomial time? 4) Variants on boxicity 2 (Sri) What happens when you change the definition of boxicity? Some variants include eliminating the isoorientation, equal sized boxes, squares, "nestable" boxes, no proper containment of boxes, small integer coordinates. Can you prove that you change the set? Can you recognize and find algorithms for any of these variants? 5) Optimization in Boxicity 2 Graphs How fast is clique for boxicity 2 graphs (in P because the number of maximal cliques is O(n^2)), both with and without the representation? Independent set, boxicity 2, also looks like it should be easy at least if given the representation, but I can't see it off the top of my head. 6) Weakly triangulated astroidal triple-free graphs This generalizes interval graphs; open problems include recognition, optimization, counting the number, and finding a representation. Perfect Graphs and Variants I won't even include the famous ones; perfect graph conjecture, recognize perfect graphs, recognize Berge graphs, recognize odd hole free graphs 1) Optimizing perfectly orderable graphs (Chvatal) Is there a "combinatorial" polynomial-time algorithm to find a maximum independent set in a graph G, when you are also given a perfect order on G. By combinatorial, I mean that you do not use ellipsoid techniques; since all perfectly orderable graphs are perfect, the algorithm of Gr$roman o dotdot$tschel Lovasz and Schrijver finds a maximum independent set in polynomial time using the ellipsoid method. What if no order is given? Of course, this is open for general perfect graphs as well. Permutation Graphs 1) Covering Graph Equivalent of Permutation Graph (Spinrad) Given an undirected graph, can the edges be directed to be the covering graph of a 2 dimensional partial order? See if you can determine this in polynomial time. The problem is also relevent for covering graph of other classes, such as N-free or interval orders. 2) Find a "large" independent set or clique It is well known that you can find an independent set or clique of size at least n^.5. Cab you find some such in O(n) time? Similar question for perfect graphs; can you find such a set quickly? The set does not need to be maximum, of course, and for comparability graphs (must beat matching). 3) Number of Prime Permutation Graphs(Stewart) What percentage permutation graphs are prime, i.e., have a unique representation? As opposed to arbitrary graphs, the percentage of nonprime graphs does not go to 0 for large values of n, but does the percentage of prime permutation graphs go to 0? 4) Circular Permutation Graphs (Sritharan) Optimization problems, generalizations to k concentric circles 5) Astroidal triple-free co-AT-free graphs Generalizes the comparability cocomparability characterization. Open problems include recognition, optimization, counting, representation. Representations 1) Distance Hereditary Graphs Find an intersection representation 2) Hereditary and 2^O(nlogn) =>? Implicit Representation(Kannan,Naor,Rudich) Open classes include containment or intersection graphs of circles, intersection graphs of lines or squares with general orientation in the plane, and many others. More generally, can you store any hereditary class with 2^f(n) members using O(log(f(n))/n bits per vertex, so that adjacency can be tested using only the information stored at the vertices in question? 3) Optimization Requiring Representation Find any example of a problem which is NP-complete on a class of graphs if the input is in adjacency list form, and polynomial if the class is given with its natural representation. Visibility Graphs 1) Maximum clique in visibility graph, given G only (Lubiw) It is O(n**3) if you are given the polygon 2) Recognition Famous open problem, not known to be in NP, still open if you are given the ordering of points on the boundary of the polygon. 3) Induced Visibility Graphs For various reasons, I feel that these are a less studied but more interesting, and possibly more tractable, class of graphs. All problems above are still open, as are some others. For starters, are the permutation/interval/chordal bipartite graphs in this class (I doubt it)? 4) Number of Induced Visibility Graphs (Spinrad) The key question here is, if G is a graph on n vertices, and G is an induced subgraph of a visibility graph H, how big can the minimum size H be? I can show it is O(nlogn$alpha$(n)), but it could be linear. It depends in part on the following question: how many visibility lines can touch the outer boundary of the polygon? There is a published paper claiming O(n), but we have found a serious error, and I think that the answer is probably O(nlogn). Can you find an efficient representation? 5) 3-clique ordering (Lubiw) Lubiw showed that every visibility graph has a "3-clique" ordering, i.e. you can start with a triangle and always continue with a vertex which is adjacent to all vertices from some previous triangle. How fast can you find such an ordering, either in a general graph or visibility graph? The obvious algorithm is something like O(n^7). Weakly Triangulated Graphs 1) Verifying weakly triangulated graphs (Spinrad) Can I verify a certificate that a graph is weakly triangulated using o(n^4/log^.5n) time? This seems like it could be easier than the larger problem of recognizing in o(n^4) time. 2) Weakly Triangulated Comparability Graphs (Sri) Recognize, count the number, find an efficient representation. Contains chordal bipartite graphs. 3) Every weakly triangulated graph without P5 is perfectly orderable (Chvatal) Resolve this conjecture. 4) G s.t. all induced subgraphs have a simplicial or cosimplicial vertex (Sri) Recognition, optimization, etc. Other Classes 1) Claw-free recognition As far as I know, you need to beat beat n * MM; do not expect to beat O(MM), where MM is the time to perform matrix multiplication 2) Circle intersection graphs (Golumbic) Apparently, almost nothing is known about the intersection graphs of circles in the plane, so recognition, structural characterization, and representation problems are all open. 3) $B sub 1$-orientation (Urrutia) An undirected graph is $B sub 1$ orientable if the edges can be directed so that (u,v), (w,v) implies that u and w are adjacent in G. These graphs include among other classes the chordal graphs and circular-arc graphs. Can you recognize these in o(nm) time? For the nonalgorithmically inclined, Urrutia has this conjecture: if G is $B sub 1$ orientable, then G is the intersection graph of subtrees of a planar graph. 4) P5 and P5 Complement free Generalizes cographs in much the same way that weakly triangulated graphs generalize chordal graphs. 5) Forbidden Submatrices Consider matrices which can be permuted to avoid a specific submatrix. Can you count the number of matrices, and give a nice representation? I am especially interested in forbidding the 2 by 2 identity matrix; recognizing these faster than O(c^2r^2) is of interest as well. 6) Brittle Graphs (Eschen) G is brittle if for all induced subgraphs, there is either some vertex which is not the endpoint of any $P sub 4$ or there is some vertex which is not the midpoint of any $P sub 4$. Recognize in o(m^2). 7) Independent sets in well Covered Graphs (Spinrad) A well covered graph is a graph in which every maximal independent set is maximum. If you know G is well covered, it is trivial to find a maximum independent set in G, but recognizing well-covered graphs is co-NP-complete. Find a polynomial algorithm which either finds a maximum independent set in G, or answers that G is not well-covered. 8) Containment Graphs, Paths in a Tree Recognize efficiently. 9) Recognize intersection G of subgraphs of 2-trees

Send comments or new problems to include to spin@vuse.vanderbilt.edu