Please mail me with any corrections, or any other comments. The list is
very rough at the moment.
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.
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).
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
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
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?
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.
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
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,
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
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
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.
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.
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.
1) Maximum clique in visibility graph, given G only (Lubiw)
It is O(n**3) if you are given the polygon
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
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.
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
9) Recognize intersection G of subgraphs of 2-trees
Send comments or new problems to include to