# 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*^{2} is the
graph on the same set of vertices where two vertices
in *G*^{2} 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*^{2})≤ O(tw*(G) + *D*(G))*