Ignasi Sau Valls: Finding small subgraphs of given minimum degree
Vir: Seminar za teorijo grafov in algoritme
V četrtek ob 12:30 v 3.07 govori Ignasi Sau Valls iz CNRS/UNSA in
INRIA - Sophia-Antipolis, FRANCE. Naslov predavanja je:
Finding small subgraphs of given minimum degree
Povzetek: This talk deals with degree-constrained subgraphs problems. In general, given an input graph G, these problems consists in finding a connected subgraph H of G satisfying some degree constraints and optimizing some parameter (usually |V(H)| or |E(H)|). In the talk we will present some results about hardness and approximation of one of the problems belonging to this family.
Namely, the "Minimum Subgraph of Minimum Degree d" (MSMD_d for short) problem consists in, given a graph G and an integer d, finding a
smallest subgraph of G (in terms of the number of vertices) with
minimum degree at least d. For d=2 it corresponds to finding a
shortest cycle of the graph, which can be done in polynomial time. For
d > 2 the problem becomes NP-complete. We will prove that MSMD_d is not in APX for any fixed d > 2, using the error amplification
technique. If time permits, we will also explain an O(n/logn)-approximation algorithm for the classes of graphs excluding
a fixed graph as a minor.
This is joint work with Omid Amini, David Peleg, Stephane Perennes,
and Saket Saurabh.