Abstract:

In the talk we briefly describe two independent problems: 

1. Optimal Permutation Routing on Plane Grids 

In the permutation routing problem, each processor is the origin of at most
one packet and the destination of no more than one packet. The goal is to
minimize the number of time steps required to route all packets to their
respective destinations. We study this problem in a hexagonal network, i.e.
a finite subgraph of a triangular grid, which is a widely used network in
practical applications. We will present an optimal distributed routing
algorithm for  full-duplex hexagonal mesh networks. Furthermore, we will
prove that this algorithm is oblivious and translation invariant. Finally,
we will discuss extensions to other plane grids.

[joint work with Janez Zerovnik]


2. The Minimum Subgraph of Minimum Degree at least d (MSMDd) problem

We study the problem of Minimum Subgraph of Minimum Degree at least d (or
MSMDd): Let d be a natural number, and G = (V,E) a given graph. The problem
is to find a subset S of vertices of minimum size in G, such that G[S] has
minimum degree at least d.

Asking this question for d=2 is finding the girth of a graph (length of the
shortest cycle), which is well known to be polynomial. We will prove that
for d at least 3, MSMDd does not accept any constant factor approximation
(that is, it is not in APX). We will also comment two other results: 
(1) MSMDd is W[1]-hard for d at least 3 (i.e. we cannot expect to find FPT
algorithms for a general graph),
(2) There exist FPT algorithms for minor free graphs (using a dynamic
programming approach).

[joint work with Omid Amini and Saket Saurabh]