The Maximum Independent Set problem on intersection graphs & Covering minimum cost arborescences

Speaker(s)

Anna Zych & Attila Bernath

Affiliation

Uniwersytet Warszawski

Date

May 31, 2012, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

The Maximum Independent Set problem on intersection graphs

I will talk about the Maximum Independent Set problem on intersection
graphs. An independent set is a set of vertices in the graph that are
pairwise disjoint. In general graphs, the problem of finding the
maximum independent set of vertices is hard to approximate within a
ratio asymptotically better than 1/|V|, where V is the set of vertices
of the graph. However the instances we get in reality are often not
that pessimistic. Sometimes, for some routing or planning purposes, we
care to find a maximum set of geometric objects in the plane that do
not intersect. An intersection graph is a graph where the vertices
correspond to shapes given in the plane and there is an edge between
two vertices iff the corresponding shapes intersect. In particular,
every planar graph is an intersection graph of stars. A lot of classes
of intersection graphs have been defined depending on the type and the
location of the objects in the plane. For most of these classes the
hardness status of the Maximum Independent Set problem is known. This
is not the case, however, for the class of outerstring graphs,
although the Independent Set problem on outerstring graphs models many
realistic routing scenarios. I will end up presenting a step forward
to determining the hardness of this problem, which is a polynomial
time algorithm for the Maximum Independent Set in outersegment graphs
(a subclass of outerstring graphs). The main purpose of this talk is
to wake the interest to solve the problem in outerstring graphs.

=========================

Covering minimum cost arborescences

Given a digraph $D=(V,A)$ with a designated root node $r\in V$ and
arc-costs $c:A\to \Rset$, we consider the problem of finding a minimum
cardinality subset $H$ of the arc set $A$ such that $H$ intersects
every minimum $c$-cost $r$-arborescence. (By an $r$-arborescence we
mean an inclusionwise minimal subset of arcs of $D$, in which every
node is reachable from $r$.)

This problem is a special case of covering minimum cost common bases
of two matroids, which is NP-complete even if the two matroids
coincide, and the costs are all equal to 1. On the other hand we show that this special case is polynomially solvable: we give a polynomial algorithm for finding such an arc set $H$. The algorithm solves a weighted version as well, in which a nonnegative weight function $w:A\to \Rset_+$ is also given, and we want to find a subset $H$ of the arc set such that $H$ intersects every minimum $c$-cost $r$-arborescence, and $w(H)$ is minimum.

This is a joint result with Gyula Pap.

---