Open Problems from Wlab05

Sang-il Oum

Suppose that a function on subsets of a finite set V satisfies the following three conditions.

• f(X)+f(Y) ≥ f(X cap Y)+f(X cup Y) for all subsets X and Y of V
• f(emptyset)=0
• f({v}) ≤ 1 for all v in V
• f(X)=f(V-X) for all subsets X of V

Is there a polynomial-time (in |V|) algorithm that recognizes a function f having branch-width at most 3 (assuming that f is given by the oracle function such that a single query takes a unit time)?

Note: For 0, 1, and 2, there are simple algorithms.

J. Jerebic, S. Klavzar, D. F. Rall

A graph is called distance-balanced if for every edge uv the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. Classify distance-balanced graphs among the generalized Petersen graphs.

P. Hlineny

Can you compute the crossing number of a graph efficiently in the case that (any reasonable) "width" parameter of the graph is bounded?

Alternatively, can you prove NP-completeness of crossing number for graphs with a fixed value of some "width" parameter? As the "width" parameter, one may substitute tree-width, clique-width, path-width, cutwidth, etc...

(This problem is based on the original question of Seese concerning crossing number and tree-width.)

Daniel Lokshtanov

If k is length of longest isometric cycle of G, is there a positive constant c so that treelength(G) < c*k?

For which graph classes is it easy to determine whether G has H as an isometric subgraph?

Find an efficient exact algorithm for determining whether G has H as an isometric subgraph.

Dimitrios Thilikos

If G is a graph, then its "square" G² is the graph on the same set of vertices where two vertices in G² are adjacent if they share a neighbor in G. By D(G) we denote the maximum degree of G.

Prove or disprove:

For any graph G, tw(G²)≤ O(tw(G) + D(G))