









\documentstyle{article}
 \title{THIRD ANNUAL DONET MEETING 1996}
\author{}
%\date{}


\sloppy




\begin{document}

\maketitle

\bigskip


\addtolength{\oddsidemargin}{-2.1cm}
\addtolength{\evensidemargin}{-2.1cm}
\addtolength{\topmargin}{-2.4cm}




\section {PREFACE.}


Welcome to the third Annual Meeting of the Discrete Optimization Network (DONET)
 at Stirin Castle in the Prague Area, May 19-24, 1996.
This is the last of the DONET Annual meetings 
 within the present framework of 
DONET. The previous annual meetings were held in Trento in 1993
and in London in 1995.  These were of course not the only activities 
 of the network and an interested reader 
may trace some of the other highlights (such as a conference in Annecy) in the activity report of 1995 which
is included below. We would like to thank to Bruce Reed for
 providing us with it. We enclose a program of our 1996 meeting
 together with the abstracts
 of the talks. One can see 
 that DONET contributed in an essential way to the development of Discrete Optimization in Europe especially by providing 
 opportunities for the critical group of young researchers.
 We hope that we shall be able to
continue and deepen our activity in the future.
 Finally we would like to thank  to all the
local coordinators for their support in preparing this conference.

\bigskip\noindent 

\rightline{ Martin Loebl ~~  Jaroslav Ne\v set\v ril~~~~~~}

\newpage



\vspace*{3cm}


\section {CONTENTS.}

% {\bf 1. PREFACE.}
%
% \noindent {\bf 2. CONTENTS.}
%
% \noindent {\bf 3. INVITED SPEAKERS AND PROGRAM.}
%
% \noindent {\bf 4. ABSTRACTS.}
%
% \noindent {\bf 5. LIST OF PARTICIPANTS.}
%
% \noindent {\bf 6. DONET ANNUAL REPORT 1995.}



\def\contentsname{~}
\bigskip\bigskip
\tableofcontents

\newpage





\section{\mbox{DONET MEETING PRAGUE,} \mbox{MAY 19--24 1996.}}


\bigskip

\noindent{\bf INVITED SPEAKERS.}
\bigskip


Andr\'{e} Bouchet, University of Le Mans

Peter J. Cameron, Queen Mary and Westfield College 

(non-Donet participant) 

Michele Conforti, University of Padova

Gerard Cornuejols, University of Toulouse and 

Carnegie Mellon University (non-Donet participant)

Bert Gerards, CWI, Amsterdam

Winfried Hochstaettler, University of Koeln 

(non-Donet participant)

Andras Frank, Eotvos University, Budapest

Monique Laurent, LIENS, Paris

Martin Loebl, Charles University, Prague

Andras Sebo, University Joseph Fourier, Grenoble

Bruce Shepherd, LSU, London

Bruno Simeone, University La Sapienza, Rome

Robin Thomas, Georgia Institute of Technology, Atlanta 

(non-Donet participant)

Carsten Thomassen, Technical University Danemark 

(non-Donet participant)

Dominic Welsh, University of Oxford 



\newpage

\noindent{\bf PROGRAM}


\bigskip\noindent
{\bf Monday morning 9 a.m.} 

 Robin Thomas

 Bert Gerards

 Colin McDiarmid

\bigskip\noindent
{\bf Monday afternoon 4 p.m.}

 Bruce Shepherd

 Jens Vygen

 Gautam Appa

\bigskip\noindent
{\bf Tuesday morning 9 a.m.}

 Dominic Welsh

 Carsten Thomassen

 Martin Loebl

\bigskip\noindent
{\bf Tuesday afternoon 4 p.m.}

 Monique Laurent

 Winfried Hochstaettler

 Willem Haemers


\bigskip\noindent
{\bf Wednesday morning 9 a.m.}

 Bruno Simeone

 Andras Frank

 Kyri Kilakos

 Anjai Kapoor

\bigskip\noindent
{\bf Thursday morning 9 a.m.}

Gerard Cornuejols

Michele Conforti

Andras Sebo

\bigskip\noindent
{\bf Thursday afternoon 4 p.m.}

 Denis Naddef

 Sandor Fekete

 Jorgen Bang-Jensen


\bigskip\noindent
{\bf Friday morning 9 a.m.}

 Andre Bouchet

 Peter Cameron



\newpage




\section{DONET MEETING PRAGUE: THE ABSTRACTS.}


\bigskip


\def\s{\bigskip\bigskip}
\def\se{\bigskip\bigskip}
\def\sa{\nopagebreak\medskip\nopagebreak}
\def\sb{\nopagebreak\medskip\nopagebreak}
\def\sc{\nopagebreak\bigskip\nopagebreak\noindent}



\centerline{\bf Gautam Appa}
\sa
\centerline{\bf Bimodular Network Matrices} 
\sb
\centerline{\it LSU, London}
\sc
Network matrices provide an important class of totally unimodular matrices which
arise as a natural extension of the node-arc incidence matrices of directed graphs.  They can
be interpreted as arc-path incidence matrices in which each column represents the unique path
between a pair of vertices in a directed tree graph, while rows represent the arcs of the tree
graph.  We provide a similar extension for the node-edge incidence matrices of undirected
graphs.  
      The node-edge incidence matrix (call it N) of an undirected graph, consisting of
exactly two $+1$ entries in each column, has two important properties.  
First, $N$ is totally
bimodular, i.e., any square sub-matrix of $N$
 has a determinant  $0$ or $2k$ where $k$ is any non-
negative integer.  Second, $N$ is $2$-integral.  Non-singular submatrices of $N$
contain, in general, decomposable balanced sub-matrices of type $R1$ with determinant $q1$ or
type $R2$ with determinant $q2$.  We identify the graphical structure of each type.  $R1$ represents
the incidence matrix of a tree graph augmented by one self-loop, while $R2$ turns out to be the
incidence matrix of a connected graph with exactly one odd cycle of length 
 at least three.  We
concentrate on the only new structure in this setting, viz., incidence matrices of connected
graphs with exactly one odd cycle of length three or more.  Let $G$ represent a connected
graph with $n$ nodes and $n$ edges, having exactly one such odd cycle.  Then we define
generalised paths/tours involving any two nodes of $G$, and write a bimodular network matrix,
called BINET and denoted by $B$, as the edge-tour incidence matrix of these generalised tours. 
In general, elements of $B$ are $0, q1$ and $q2$.  
      We show that a binet matrix $B$ is totally bimodular and 2-integral.  We show
connections to the ternary packing and covering problems.  
      One surprising result shown is that one of the two five by five
 unimodular matrices, known
not to be a network matrix, is a binet matrix.




\s

\centerline{\bf Jorgen Bang-Jensen}
\sa
\begin{center}{\bf A Polynomial Algorithm For The Hamiltonian Cycle Problem
For Semicomplete Multipartite Digraphs}\end{center}
\sb
\centerline{\it Odense University, Denmark}
\sc
A {\em semicomplete digraph} is a digraph whose
underlying
graph is complete. A {\em semicomplete multipartite digraph} is
a digraph 
that can be obtained from some  semicomplete digraph $D$ by
choosing a spanning collection of vertex disjoint induced 
subgraphs of $D$ and
deleting all arcs inside each of these.
When the number
of subgraphs above is precisely two, we obtain the 
{\em semicomplete bipartite digraphs}.
 While the Hamiltonian cycle problem is very easy for
semicomplete digraphs and relatively easy for semicomplete
bipartite
digraphs (in which case there is still a nice mathematical
characterization), it has been an open problem for more than 10 years in
the case of semicomplete multipartite digraphs. Recently the authors have
proved (constructively) that there is a polynomial algorithm
 for the Hamiltonian
cycle problem for semicomplete multipartite digraphs.
In this talk we will give the necessary background and, if time
permits,  a very
brief sketch of the algorithm.



\s

\centerline{\bf Andr\'{e} Bouchet}
\sa
\centerline{\bf Tight Multimatroids} 
\sb
\centerline{\it University of Le Mans}
\sc
A multimatroid is a combinatorial structure that unifies the properties
of delta-matroids and the properties of the Euler tours of 4-regular
graphs. We originally introduced this structure to unify a theorem of
Jackson on the existence of three orthogonal Euler tours in a 4-regular
graph with a theorem of Edmonds on the existence of a covering of a
matroid with a given number of independent sets.

Here we focus on the subclass of tight multimatroids. These
multimatroids can be locally described by a simple graph, called
fundamental graph, in the vicinity of any base. The 2-matroids
associated to the even delta-matroids and the 3-matroids associated to
4-regular graphs are tight.

The transformations of a fundamental graph, when the base is changed,
are compared to two local transformations of simple graphs: the local
complementations and the edge-pivotings. By using these transformations
it is possible to extend to tight multimatroids some of the connectivity
properties known for matroids.




\s
       
\centerline{\bf Peter J. Cameron}
\sa
\centerline{\bf Derangements in Permutation Groups}
\sb
\centerline{\it Queen Mary and
Westfield College}
\sc
It is well known that the number of derangements in the
symmetric group on $n$ letters is very close to $n!/{\rm e}$
for moderately large $n$. What about other permutation groups?

In the finite case, it follows from the orbit-counting lemma
that the vector giving the probability that a random group
element has $i$ fixed points ($i=1, \ldots, n$) is related
to the vector whose $i$-th coordinate is the ratio of the
number of orbits on $i$-tuples to the total number of $i$-tuples,
by a binomial transformation. This can be used to find estimates
for the proportion of derangements in some cases.

More interesting is the possibility of extending these results
to infinite permutation groups. Sometimes, the above formalism
provides an explicit number, but it is not clear what this
number has to do with derangements. For example, for the
infinite symmetric group we do indeed obtain $1/{\rm e}$,
as expected; but for the group of order-preserving permutations
of the rational numbers, we obtain $1/2$.



\se



\centerline{\bf Michele Conforti}
\sa
\begin{center}{\bf A Theorem of Truemper about Wheels and Three-Path
 Configurations}\end{center}
\sb
\centerline{\it University of Padova}
\sc
Suppose one has to "sign" the edges of a graph with
even an odd labels so that, for each chordless cycle
H, the parity of the set of odd edges of H satisfies a
given requirement (is even, is odd).
Klaus Truemper has proven an important theorem about
the minimal forbidden subgraphs for this property.
We give a novel and easy proof for this result. 
We also describe several applications of this
theorem: In particular,

-The characterization of Tutte of regular matroids
and  Reid for matroids representable over GF3

-The characterization of universally signable ghraphs

-The characterization of balanceable graphs

-The characterzation of the graph that can be signed
so that every
hole is either even or odd.

These results were jointly obtained with Cornuejols,
Kapoor and Vuskovic.



\s


\centerline{\bf Gerard Cornuejols}
\sa
\centerline{\bf Ideal and Balanced Matrices}
\sb
\centerline{\it University of Toulouse and Carnegie Mellon University}
\sc
A $0,1$ matrix $A$ is perfect if the polytope $\{x \leq 0:
Ax \leq 1\}$ is an integer polytope. It is ideal if
$\{x \geq 0: Ax \geq 1\}$ is an integer polyhedron. It is 
balanced if no square submatrix of odd order contains
exactly two ones per row and per column. In this 
talk, we survey results and open problems about 
these and related classes of matrices.



\se

    
\centerline{\bf Bert Gerards}
\sa
\centerline{\bf The Matroids Representable Over The 4-element Field} 
\sb
\centerline{\it CWI, Amsterdam}
\sc
Together with Jim Geelen and Ajai Kapoor, we present the complete list
of forbidden minors for GF(4)-representable matroids.





\s


\centerline{\bf Willem Haemers}
\sa
\centerline{\bf Disconnected vertex sets in graphs} 
\sb
\centerline{\it Tilburg University}
\sc
Let $A$ and $B$ be two disjoint vertex sets of a graph $G$ such that 
there are no edges between $A$ and $B$.
We give an upper bound for $|A|\cdot|B|$ in terms of eigenvalues of
matrix representations $G$.
This leads to a lower bound for the bandwidth of $G$ and to
an upper bound for equidistant code pairs in an association scheme.




\s


\centerline{\bf Winfried Hochstaettler}
\sa
\centerline{\bf On Bases of Circuit Lattices} 
\sb
\centerline{\it University of Koeln}
\sc
This is joint work with Martin Loebl.
Given a binary matrix $B$ the circuit lattice of the corresponding
binary matroid is the integer hull of the $0,1$-vectors in the kernel of
$B$. We discuss a couple of observations concerning the following
conjecture: The circuit lattice of a binary matroid has a basis of
$0,1$-vectors or, in other words, the integer lattice of a binary code has
a basis of codewords.

We relate this conjecture to a certain Sylvester-type Hadamard matrix $M$
and prove a duality statement about submatrices of full row length.

Finally, we disprove a stronger version of the above conjecture,
indicating, that it, if true, does not have a local character.




\se


\centerline{\bf Sandor Fekete}
\sa
\centerline{\bf Angle-Restricted Tours in the Plane} 
\sb
\centerline{\it University of Koeln}
\sc
Earlier this year, Aggarwal, Coppersmith, Khanna, Motwani, and
Schieber showed that the so-called ``Angular-Metric TSP'' is
NP-complete. In this problem, one has to find a Hamiltonian path for a given
set of points in the Euclidean plane, such that the sum of the direction
changes at each vertex along the tour is minimized.
This result has important consequences for the problem of matroid parity,
as it resolves the long-standing open question about the hardness of the
weighted linear matroid parity problem in the affirmative.

The Angular-Metric TSP is closely related to the problem
``Angle-Restricted Tour'' (ART):
For a given set $A\subseteq\ (-\pi;+\pi]$ of angles, we have
to decide whether a set $P$ of $n$ points
in the Euclidean plane allows a closed directed tour consisting of straight
line segments, such that all angles between consecutive line segments are
from the set $A$.

We present a variety of algorithmic and combinatorial results on this
problem.
In particular, we show that any finite set of at least five points in general
position allows
a ``pseudoconvex'' tour (i.\,e.\ a tour where all angles are nonnegative),
and we derive a fast algorithm for constructing such a tour.
Moreover, we give a complete classification (from the computational
complexity point of view) for the special cases where the tour has to be
part of the orthogonal grid.

The paper presented is joint work with Gerhard Woeginger (Graz).




\s
           

\centerline{\bf Andras Frank}
\sa
\centerline{\bf Orientations of Graphs And Submodular Flows} 
\sb
\centerline{\it Eotvos University, Budapest}
\sc
We briefly summarize the known link between submodular
flows and orientation problems of undirected graphs. A simplified feasibility
theorem will then be   shown for
submodular flows constrained by crossing submodular functions. As an
application we derive an extension of a new orientation result of
Nash-Williams.





\s

\centerline{\bf Anjai Kapoor}
\sa
\centerline{\bf Triangle Free Graphs That Are Odd-Signable} 
\sb
\centerline{\it University of Padova}
\sc
A graph is odd-signable if there exists 
an assignment of "odd" and "even" labels to the
edges so that every hole has an odd number of odd
edges. Graphs with no even holes are a subclass of
this class. Triangle-free (TF) odd-signable graphs form a class of basic graphs for 
cap-free odd-signable graphs, which in turn are a
basic class in the study of graphs with no even
holes. 

Here we give a decomposition theorem and recognition
algorithm for TF odd-signable graphs. We also show
that all TF odd-signable graphs can be constructed
by a sequence of "ear additions". We make some
conjectures regarding the description of the stable
set polytope for these graphs.

These results were jointly obtained with Cornuejols,
Conforti and Vuskovic.





\s

\centerline{\bf Kyriakos Kilakos}
\sa
\centerline{\bf Polytopes of Bounded Stable Sets} 
\sb
\centerline{\it LSU London}
\sc
The {\em $t$-stable set polytope} of a graph is the convex hull  of incidence
vectors of stable sets of cardinality at most $t$ in the graph.
For $t=3$, we describe the facet defining inequalities of the
$t$-stable set polytope of any bipartite
graph $G$.  In addition, we show that 
for any integral weighting on the vertices of $G$, the chromatic
number of $G$ (with respect to this weighting) is equal to the
round up of its fractional chromatic number plus one.

\medskip
More generally,  for any integer $t$,
we discuss  facet defining inequalities of the 
$t$-stable set polytope  of bipartite graphs.


\s

\centerline{\bf Monique Laurent}
\sa
\begin{center}{\bf In memory of Svata Poljak: Positive Semidefinite Programming
 For Max-Cut, Geometric Results}\end{center}
\sb
\centerline{\it LIENS, Paris}
\sc
This talk is devoted to results obtained jointly with
Svata Poljak on the geometry of the semidefinite relaxation
for the max-cut problem.
Svata had, in fact, introduced me to this topic in September 1993 at
the occasion of a one month visit in Paris and  our collaboration
continued thereafter.

\medskip
Positive semidefinite programming has been applied successfully 
for several combinatorial optimization problems, in particular,
for  the maximum stable set problem in perfect graphs
(by the work of Gr\"otschel, Lov\'asz and Schrijver)
and, more recently, for the max-cut problem.
Goemans and Williamson have shown  how to design good 
and efficient approximation algorithms  for max-cut 
 by optimizing over the {\em elliptope} 
${\cal E}_n$, which is the set of $n\times n$ symmetric positive
semidefinite matrices with diagonal entries one.
Since then, it has been recognized that 
similar techniques apply for several other problems (such as max 2-sat, 
graph coloring, max $k$-cut, 
or maximum bisection problems)  using  the elliptope
with possibly some additional linear constraints.

Our work with Svata focused, in particular, on trying to understand
the geometry of the elliptope ${\cal E}_n$. In particular,
we described its vertices (i.e., the points with 
full dimensional normal cone; they are precisely the
cuts)  and the spectrum of its face dimensions
(and for its polyhedral faces as well). 
%The elliptope ${\cal E}_n$  forms a (nonpolyhedral) relaxation
%of the cut polytope which retains however some of its features.
We also considered the following further aspects:
 link with the TH-body underlying the positive semidefinite
relaxation for the maximum stable set problem,
possible tightening of the 
 elliptope using the gap inequalities, 
description in closed form of projections of the elliptope 
for certain classes of graphs (in connection with completion
problems for positive semidefinite matrices in linear algebra).




\s

\centerline{\bf Martin Loebl}
\sa
\centerline{\bf On Pfaffian Orientations of Graphs} 
\sb
\centerline{\it Charles University, Prague}
\sc
This is joint work with Anna Galluccio. We present a theory of  Pfaffian 
 orientations of graphs and their linear combinations, proposed by Kasteleyn 
 in the beginning of the 60's. It has strong consequences for 
 the enumeration of perfect
 matchings, for the Max Cut problem and the Ising Spin Glasses.
 We will discuss separately the problem of Pfaffian orientations of bipartite
 graphs which is equivalent to the even cycle problem.




\se



\centerline{\bf Colin McDiarmid}
\sa
\centerline{\bf Colouring Proximity Graphs in The Plane} 
\sb
\centerline{\it University of Oxford}
\sc
Given a set $S$ of points in the plane, and given $d>0$,
let $G(S,d)$ denote the graph with vertex set $S$ and with distinct
vertices adjacent whenever the Euclidean distance between them is less
than $d$.
We are interested in colouring such `proximity' or `interference'
graphs.  One application where this
problem arises is in the design of mobile telephone networks,
when we need to assign radio frequency bands (colours) to transmitters
(points in $S$) to avoid interference.
We find for example that, if the set $S$ has density $\sigma$, then
the chromatic number $\chi$ satisfies
$\chi(G(S,d))/d^2 \rightarrow \sigma \sqrt{3}/2$
as $d \rightarrow \infty$.
This is joint work with Bruce Reed.




\s


\centerline{\bf Denis Naddef}
\sa
\centerline{\bf Discovering The TSP Polytope}
\sb
\centerline{\it University Joseph Fourier, Grenoble}
\sc
In this talk, which is inspired greatly by discussions with Yves
Pochet of CORE, I will try to give you a feeling of what most of the known
valid inequalities for that polytope say. I will end by my favorite
conjecture on that polytope.




\se


\centerline{\bf Rudi Pendavingh}
\sa
\centerline{\bf A Polynomial Time Algorithm For Bibranching}
\sb
\centerline{\it University of Amsterdam}
\sc
This is  joint work with J. Keijsper.
Let $D=(V,A)$ be a digraph, $W\subset V$ a subset of its vertices.
A {\it bibranching} is a set $B\subset A$ such that
\begin{enumerate}
\item  for all $v\in W$, $B$ contains a directed path from $v$ to a vertex in
$V\setminus W$, and
\item  for all $v\in V\setminus W$, $B$ contains a directed path from a vertex in $W$ to 
$v$.
\end{enumerate}
\par\noindent For $W=\{r\}$, a bibranching is exactly an $r$-branching, i.e. a directed
tree rooted at $r$. Given a bipartite
graph, let $W$ be one of the colour classes and orient all arcs away from $W$. A set of
arcs is a
bibranching of the resulting digraph iff it is an edge cover of the original graph.
\par Now let $w$ be a positive integer weight function on the arrow set.
 Then, the linear programming duality equation for minimum weight bibranching
 has integral optimum solutions.
We will present a primal-dual algorithm for constructing a bibranching 
of minimum 
weight in polynomial time.




\s

\centerline{\bf Andras Sebo}
\sa
\centerline{\bf Gaps and Jumps} 
\sb
\centerline{\it University Joseph Fourier, Grenoble}
\sc
{\it Jump systems} have been recently defined by Bouchet and Cunningham,
as a generalization of matroids (and delta-matroids).  The convex hulls
of these constitute the most general class of polyhedra for which the
greedy algorithm works, and include integral (generalized) polymatroids;
on the other hand they do not contain all integer vectors of their
convex hull, and those which they do not contain -- called {\it gaps} --
have a particular shape, and allow to include problems like the
existence of graph factors and several tempting open problems
  Jump systems are determined by one simple
axiom.
 
In the talk I would first like to explain the fundamental results of
Lov\'asz proved at a meeting last summer (partially supported by DONET).
These show that jump systems provide a framework for several important
results and problems of combinatorial optimization.
 
Then I will show some  results of Cunningham, Geelen and Seb\H o, using
Lov\'asz's toolbox and requiring further work. For instance I will
show that every gap is the average of two closest points of the jump
system, and  derive several consequences.





\s

\centerline{\bf Bruce Shepherd}
\sa
\centerline{\bf A Node capacitated routing problem arising in local}
\centerline{\bf optical networks}
\sb
\centerline{\it LSU, London}
\sc
We discuss several problems arising in network routing
and design. In particular we consider a node-capacitated
routing problem related to ring networks of passive optical
networks.




\s

\centerline{\bf Bruno Simeone}
\sa
\centerline{\bf Generation of all $k$-partitions of an $n$-set in amortized
constant}
\centerline{\bf time per partition}
\sb
\centerline{\it University La Sapienza, Rome}
\sc
This is a joint work with Fabio Grasso. The present paper deals with the sequential generation of all $k$-partitions of an $n$-set, for a fixed 
 $1 \leq k \leq n$. The fastest known algorithm for this task is due to
 Ehrlich: it takes $O(k)$ time per partition. Here we propose another algorithm
 which takes only amortised constant time per partition. The algorithm
 is a modification of a previous procedure described by Nijenhuis and Wilf.
 We give an implementation which makes use of simple data structures, requires only $2n + k +c$ memory locations, where $c$ is a small constant, 
 and achieves the above time bound. Such bound is established
 through a careful analysis of the changes between any two consecutive
 partitions.  
 



\s

\centerline{\bf L. A. Sz\'{e}kely}
\sa
\begin{center}{\bf The number of nucleotide sites needed to accurately reconstruct
 large evolutionary trees}\end{center}
\sb
\centerline{\it Eotvos University, Budapest}
\sc
This is joint work with M. A. Steel  and P. L. Erd\H{o}s.
Biologists seek to reconstruct evolutionary trees for increasing numbers of
species, $n$, from aligned genetic sequences.  How
fast the sequence length $N$  must grow, as a function of $n$, in order to 
accurately
recover the underlying tree with probability $1-\epsilon$, 
if the sequences evolve according to simple
stochastic models of nucleotide substitution?  We show that for certain models,
the sequence length $N$
can grow surprisingly slowly with $n$ 
(sublinearly for a wide range parameters, and even
as a power of $\log n$ in a narrow range, which roughly  meets the lower bound
from information theory). By contrast, a more traditional technique (maximum 
compatibility)
provably requires $N$ to grow faster than linearly in $n$. Our approach is
 based on
a new, and computationally efficient approach for reconstructing 
phylogenetic trees from aligned DNA sequences.




\se


\centerline{\bf Robin Thomas}
\sa
\centerline{\bf Packing directed circuits} 
\sb
\centerline{\it Georgia Institute of Technology}
\sc
In joint work with Bruce Reed, Neil Robertson and Paul Seymour 
we have proved a conjecture of Younger, that for every integer
$n \geq 0$ there exists an integer $t \geq 0$ such that
for every digraph $G$, either $G$ has $n$ vertex-disjoint
directed circuits, or $G$ can be made acyclic by deleting at most
$t$ vertices. In this talk I will give motivation for the conjecture,
and outline the proof.



\s

\centerline{\bf Carsten Thomassen}
\sa
\centerline{\bf The Graph Genus Problem } 
\sb
\centerline{\it Technical University, Danemark}
\sc
The graph genus problem is that of deciding if a given graph can be 
embedded in the surface obtained from the sphere by adding g handles. This 
problem was mentioned in the book on NP-completeness by Garey and Johnson. 
Special variants for triangulations and cubic graphs were suggested be Ringel 
and Richter, respectively. In this talk we survey constructions showing that 
these problems are NP-complete. We also discuss the maximum genus problem and 
double tracings of graphs for which there exist polynomial time algorithms.




\se

\centerline{\bf Jens Vygen}
\sa
\centerline{\bf A Linear--Time Algorithm for Partitioning
 2-Dimensional Pointsets}
\sb
\centerline{\it University of Bonn}
\sc
At the DONET Conference 1995 in London I introduced a theorem describing
the structure of the optimum solutions of a crucial problem during VLSI-placement.
I mentioned that this leads to a linear--time algorithm at least for a special
case. Today I can show how the results can be extended to the general case.

The mathematical description of the problem is as follows:
Given a finite set $S$ of points in the plane, weights $w:S\to R_+$, and
capacities $\kappa_0,\kappa_1,\kappa_2,\kappa_3$ of the four quadrants,
we are looking for a fractional partition $g:S\times\{0,1,2,3\}\to[0,1]$ 
with $\sum_{i=0}^3 g(s,i)=1$ for all $s\in S$, such that the capacity
constraints $\sum_{f(s)=i} w(s) \le \kappa_i$ ($i=0,1,2,3$) are met and
the total movement $\sum_{s\in S}\sum_{i=0}^3 w(s) g(s,i) d(s,Q_i)$ is minimized.
Here $Q_i$ denotes the $i$-th quadrant and $d$ denotes the $L_1$-distance.





\s

 \centerline{\bf Dominic Welsh}
\sa
\centerline{\bf Polynomial time randomised approximation schemes for}
\centerline{\bf Tutte-Gr\"{o}thendieck invariants}
\sb
\centerline{\it University of Oxford }
\sc
The Tutte polynomial $T(G;x,y)$ of a graph $G$ encodes numerous interesting 
combinatorial quantities associated with the graph.  Its evaluation in various 
points in the $(x,y)$ plane give the number of spanning forests of the graph, 
the number of its strongly connected orientations, the number of its proper 
$k$-colourings, the (all terminal) reliability probability of the graph, and 
various other invariants the exact computation of each of which is well known 
to be $\#P$-hard.  Here I survey the problem of finding a fully polynomial 
randomised approximation schemes for approximating the value of $T(G;x,y)$.  
In particular I shall describe recent results obtained with Noga Alon and Alan 
Frieze which will give an fpras for evaluating $T$ for any dense graph $G$, that is, 
any graph on $n$ vertices whose minimum degree is $\Omega (n)$, whenever 
$x\geq 1$ and $y\geq 1$, and in various additional points.  This region 
includes evaluations of reliability and partition functions of the 
ferromagnetic $Q$-state Potts model, and extends to linear matroids where $T$ 
specialises to the weight enumerator of linear codes.

    


 


\newpage

\section{DONET MEETING PRAGUE: THE LIST OF PARTICIPANTS.}

~


Karen Aaardal, University of Utrecht

Christopher Anhalt, University of Bonn

Gautam Appa, LSU, London

Jorgen Bang-Jensen, Odense University, Denmark 

\hskip .2in (non-Donet participant)
      
Eric Bartels,  University of Oxford

V.L.Beresnev, University of Novosibirsk

\hskip .2in (non-Donet participant)

Adrian Bondy, University of Lion

Andr\'{e} Bouchet, University of Le Mans

Michel Burlet, University Joseph Fourier, Grenoble

Peter J. Cameron, Queen Mary and Westfield College 

\hskip .2in (non-Donet participant)

Ondrej Cepek, Charles University, Prague
 
Michele Conforti, University of Padova 

Gerard Cornuejols, University of Toulouse and 

Carnegie Mellon University
 \hskip .2in (non-Donet participant)

Andrea De Vitis, University La Sapienza, Rome

Reinhard Diestel, University of Chemnitz

\hskip .2in (non-Donet participant)

Sandor Fekete, University of Koeln

\hskip .2in (non-Donet participant)

Jean Fonlupt, University Paris 6

Paolo Franciosa, University La Sapienza, Roma

Andras Frank, Eotvos University, Budapest
         
Bert Gerards, CWI, Amsterdam

Roberto Giaccio, University La Sapienza, Roma

Rebecca Gower, University of Oxford

Willem Haemers, Tilburg University

Jan van den Heuvel, LSU, London 

Petr Hlineny,  Charles University, Prague

Winfried Hochstaettler, University of Koeln

\hskip .2in (non-Donet participant)

Stan van Hoesel, University of Limburg

Hein van der Holst, CWI Amsterdam

Tibor Jordan, Eotvos University, Budapest

 Anjai Kapoor, University of Padova

Judith Keijsper, University of Amsterdam

Kyriakos Kilakos, LSU, London

Martin Klazar,  Charles University, Prague

Bernhard Korte, University of Bonn

Jan Kratochvil,  Charles University, Prague

Monique Laurent, LIENS, Paris

Robert Leese,  University of Oxford

Martin Loebl, Charles University, Prague

Andras Lukacs, Eotvos University, Budapest

Colin McDiarmid,  University of Oxford

Criel Merino, University of Oxford

Raffaele Mosca, University La Sapienza, Rome

Denis Naddef, University Joseph Fourier, Grenoble

Jaroslav Nesetril, Charles University, Prague

Steven Noble, University of Oxford

Rudi Pendavingh, University of Amsterdam

Aline Pennisi, University La Sapienza, Rome

Myriam Preissmann, University Joseph Fourier, Grenoble

Federica Ricca, University La Sapienza, Rome

Andre Rohe, University of Bonn

Irasema Sarmiento, University of Oxford
 
Andras Sebo, University Joseph Fourier, Grenoble

Bruce Shepherd, LSU, London

Mark Shepherd, University of Oxford

Bruno Simeone, University La Sapienza, Rome

Stefano Smriglio, University La Sapienza, Rome

Leen Stougie, University of Amsterdam

Laszlo Szekely, Eotvos University, Budapest

Robin Thomas, Georgia Institute of Technology, Atlanta

 \hskip .2in (non-Donet participant)

Carsten Thomassen, Technical University Danemark 

\hskip .2in (non-Donet participant)

Zsolt Tuza, Eotvos University, Budapest

Pavel Valtr, Charles University, Prague

Jens Vygen, University of Bonn

Dominic Welsh, University of Oxford 





\newpage
   
\section{ DONET ANNUAL REPORT, 1995.}


\noindent{\bf Overview}

The DO-Net network has the following three long term objectives:
\begin{itemize}
\begin {item}
further development of the theory and methods of discrete optimization
\end{item}
\begin{item}
providing a European center of excellence for the training of young 
postdoctoral researchers
\end{item}
\begin{item}
the development of algorithms and software for specific discrete 
optimization problems.
\end{item}
\end{itemize}

The immediate aim of this contract is to solidly establish the network
via intensive workng periods which have both a training component
and a collaborative research component.
The initial contract called for two such periods each year, both of
a duration between two weeks and one month. 

Two such periods were organized this year. However, a week-long
duration seemed more appropriate given the difficulty of scheduling 
longer meetings.

The first meeting was held in London, England during June and was also funded 
by the London Mathematical Society. This meeting focused on the application
of discrete mathematics to practical problems. Researchers reported on   
work in diverse areas including: railway time-tabling, VLSI chip design,
aircraft crew scheduling, fiber optic networks, and currency markets.
As at all DONET meetings, substantial blocks of time were set aside for 
collaborative research, and the seeds were sown for 
a number of joint projects, leading to at least three joint papers.

The second meeting, which
was held in Annecy, France during June and was also
funded by the Universite de Lyon, had a different flavour.
Its focus was a 25 year old conjecture concerning routing in networks.
This conjecture is intimately related to recent fundamental breakthroughs 
in routing theory  ( due to Robertson and Seymour). The conjecture had been
studied by researchers throughout the network with partial success
(see e.g. the joint paper of Reed and Shepherd on this topic which is listed 
below). The purpose of the Annecy meeting was to bring together a small 
number of researchers from throughout the network (and around the world, 
with funding provided by the Universite de Lyon ) to study the problem.
The conference was a huge success as the conjecture was proven true.
Hopefully, the techniques used will lead to further breakthroughs in this
fertile area.

Institutes throughout the network are also beginning to cooperate on more 
applied problems. We mention cellular telephone networks as a specific
example. Oxford University  using money made available 
by industrial sponsors, recently appointed a post-doctoral fellow
to study problems related to this new technology. Dr Kilakos, a 
DONET post-doctoral fellow recently appointed at the LSE also has 
experience in this area. Researchers from France visiting Oxford 
were drawn into the group. Cooperation between these three groups 
continues to grow, and has already resulted in a joint 
technical report.
Both the University of Oxford and LSE have strong links to the
telecommunications industry. In particular, Dr. Shepherd at the LSE works 
as a consultant for British Telecom. Thus, the practicality of the ideas 
generated by DONET researchers can be tested quickly, and if 
appropriate the ideas can be implemented.


Joint research was also carried out in a number of other areas,
as the attached list of joint papers shows.

Also attached are participant lists for the two conferences,
a table indicating the size of each team in the network,
and a list of visits between member institutions funded from the grant.
\vskip3.0cm


\begin{verbatim}
               The Teams of The Network

       Institution               Researchers
     London School of Economics       9
     University of Oxford             5
     CWI, Amsterdam                   6
     Universitat Bonn                 8
     Universite Paris 6               8
     Universite Joseph Fourier        6
     University La Sapienza, Rome     8
     Charles University,Prague        5
     Eotvos University, Budapest      9
\end{verbatim}




\newpage



\noindent{\bf Joint Papers}
\begin{itemize}
 
\begin{item}
G. Ausiello, E. Feuerstein, S. Leonardi, L. Stougie, and M. Talamo,. 
{\it Competitive algorithms for the on-line travelling salesman},
preprint.
\end{item}
\begin{item}
Y. Bartal, S. Leonardi, A. Marchetti Spaccamela, J. Sgall, and L.
Stougie, 
{\it Multiprocessor scheduling with rejection},
preprint.
\end{item}
\begin{item}
Y. Bartal, S. Leonardi, A. Marchetti Spaccamela, J. Sgall,and  L.
Stougie, 
{\it Multiprocessor scheduling with rejection (extended abstract)}. 
Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA 96), January 28-30, Atlanta, Georgia, USA, 1996.
\end{item}
\begin{item}
G. Brightwell and P. Franciosa, {\it On the Boolean dimension of 
spherical orders,}, preprint.
\end{item}
\begin{item}
A. Frank, A. Karzanov, and A. Sebo,
{\it On integer multi-flow maximization}, preprint.
\end{item}
\begin{item}
A. Galluccio and M. Loebl, {\it Cycles of prescribed modularity}, preprint.
\end{item}
\begin{item}
A. Gerards, and A. Sebo, 
{\it Multiflows, the cut condition and Klein's bottle}, preprint.
\end{item}
\begin{item}
A. Gerards  and F.B. Shepherd,
{\it Graphs with all subgraphs t-perfect}, preprint.
\end{item}
\begin{item}
B. Korte and J. Nesetril,
{\it Vojtech Jarnik's works in combinatorial optimization}, preprint.
\end{item}
\begin{item}
J. Kratochvil and A. Sebo, {\it Coloring precolored perfect graphs}, 
preprint.
\end{item}
\begin{item}
S. Leonardi, A. Marchetti Spaccamela,  and L. Stougie,
{\it On-line scheduling with possible rejection of jobs}, preprint.
\end{item}
\begin{item}
C. Linhares-Sales, F. Maffray  and B. Reed, {\it On planar perfectly
contractile graphs},  preprint.
\end{item}
\begin{item}
C. Linhares-Sales, F. Maffray and B. Reed, {\it On planar strict quasi-parity
graphs}, preprint. 
\end{item}
\begin{item}
C.McDiarmid and B. Reed, {\it Colouring and Euclidean Distance},preprint.
\end{item}
\begin{item}
B. Reed and  F.B Shepherd,
{\it The Gallai-Younger conjecture holds for planar graphs}, preprint.
\end{item}
\begin{item}
B. Reed, N. Robertson, P. Seymour,  and R. Thomas,
{\it Packing directed circuits}, preprint.
\end{item}
\end{itemize}

\newpage





\noindent{\bf Visits}

Attendance at intensive working periods is 
listed separately.

\begin{itemize}
\begin {item}
A. Benczur, Budapest-Grenoble, five days.
\end{item}
\begin {item}
G. Brightwell, London-Budapest, eleven days.
\end{item}
\begin {item}
T. Jordan, Amsterdam-Grenoble, five days.
\end{item}
\begin {item}
R. Hein, Amsterdam-Grenoble,  five days.
\end{item}
\begin {item}
A. Frank, Budapest-Grenoble, five days.
\end{item}
\begin {item}
A. Frank, Budapest-Bonn, eleven days.
\end{item}
\begin {item}
J. Fonlupt, Paris-Bonn, one month,
\end{item}
\begin {item}
J. Fonlupt, Paris-London, one week,
\end{item}
\begin {item}
B. Korte, Bonn-Prague, five days.
\end{item}
\begin{item}
T. Kaiser, Prague-Budapest, five days.
\end{item}
\begin{item}
J. Matousek, Prague-Budapest, five days.
\end{item}
\begin{item}
J. Matousek, Prague-Roma, ten days.
\end{item}
\begin{item}
J. Nesetril, Prague-Bonn, one year.
\end{item}
\begin{item}
J. Nesetril, Bonn-Paris, three days.
\end{item}
\begin{item}
J. Nesetril, Bonn-Rome, three days.
\end{item}
\begin{item}
B. Reed, Paris - Bonn, two weeks.
\end{item}
\begin{item}
B. Reed, Paris - Oxford, six weeks.
\end{item}
\begin {item}
A. Schrijver, Amsterdam-Paris,  two weeks.
\end{item}
\begin {item}
B. Shepherd, London-Amsterdam, five weeks.
\end{item}
\begin {item}
B. Shepherd, London-Bonn, five days.
\end{item}
\begin {item}
L. Stougie, Amsterdam-Rome, six weeks.
\end{item}
\begin {item}
J. Vygen, Bonn-Budapest, eleven days.
\end{item}
\begin {item}
Z. Szigeti, Budapest-Grenoble, five days.
\end{item}
\end{itemize}







\newpage







\noindent{\bf Participants list: Donet Meeting, London, June 26-30, 1995}
\vskip0.3cm

K. Aardal, Amsterdam

C. Albrecht, Bonn

S. Amin, BT Laboratories (non-Donet participant)

C. Anhalt, Bonn

Martin Anthony, LSE

Gautum Appa, LSE

D. Applegate, ATT Bell Labs (non-Donet participant).

J. Bang-Jensen, Odense University (non-Donet participant)

F. Barahona, IBM Research (non-Donet participant)

E. Bartels, Oxford

A. Benczur, Budapest 

Thomas Bending, Queen Mary and Westfield College 

(non-Donet participant)

Norman Biggs, LSE

Graham Brightwell, LSE

N. Christofides, Imperial College (non-Donet participant)

W. Cook, Bonn

W. Cunningham, Grenoble(visitor)

C. Van Eijl, Eindhoven (non-Donet participant)

G. Elekes, Budapest

S. Fekete, Koln (non-Donet participant)

M. Fischetti, DEI, Padua

J. Fonlupt, Paris

C. De Francesco, Padua

A. Frank, Budapest

M.X. Goemans, MIT (non-Donet participant)

C. Hurkens, Eiendhoven(non-Donet participant)

T. Jordan, Budapest

J. Keijsper, Amsterdam

Z. Kira'ly, Budapest

B. Korte, Bonn

D. LeSaint, BT Laboratories (non-Donet participant)

M. Loebl, Prague

C. Mannino, Rome

R. Marsten, Atlanta, USA (non-Donet participant)

A. Mascis, Rome

J. Matoussek, Prague

C. McDiarmid, Oxford

M. Molloy, Paris(visitor)

D. Naddef, Grenoble

G.L. Nemhauser,  Atlanta (non-Donet participant)

J. Nesetril, Prague

S. Noble, Oxford

G. Oriolo, Rome

D. Pacciarelli, Rome

A. Pacifici, Rome

R. Pendavingh, Amsterdam

S. Powell, LSE

M. Preissmann, Grenoble 

W.R. Pulleyblank, IBM research (non-Donet participant)

B. Reed, Paris

P. Riva, LSE

A. Rohe, Bonn

F. Rossi,Rome

A. Schrijver, Amsterdam

A. Sebo, Grenoble

B. Shepherd, LSE

B. Simeone, Rome 

R. Succi, Rome 

Z. Szigeti, Budapest

M. Trick Carnegie Mellon University (non-Donet participant)

P. Valtr, Prague

J. Vygen, Bonn


\newpage


\noindent{\bf Participants list: Donet Meeting, Annecy, June 16-23, 1995}
\vskip0.3cm


N. Alon, Tel-Aviv University

A. Bondy, Universite de Lyon

A. Gerards, Amsterdam

W. McCuiag, University of Toronto

C. McDiarmid, Oxford

M. Molloy, Paris (visitor)

B. Reed, Paris

P. Seymour, Bell Communications Research

B. Shepherd, LSE

R. Thomas, Paris

S. Thomasse, Universite de Lyon

S. Vempala, Carnegie Mellon University

   









\end{document}


