***** KAIST Discete Math Semianr *****

DATE: April 17th, Thursday

TIME: 3PM-4PM

PLACE: E6-1, ROOM 1409

SPEAKER: Eun Jung Kim (김은정), Royal Holloway, University of London, UK.

TITLE: Fixed-Parameter Tractability and Parameterized Minimum Leaf Out-Branching Problems

Fixed-Parameter Tractability (FPT) is a rapidly expanding framework to tackle computationaly hard problems. In many combinatorial problems, the input instance usually comes in pair with an interger k, of which the typical example is found in the VERTEX COVER: Given a graph G and an integer k, is there a VERTEX COVER of size at most k? The motivation is to restrict the presumably inevitable combinatorial explosion to be one in terms of k so that for a relatively small k the problem is expected to be solved in a reasonable amount time. Moreover paramterized framework leads to an elaborate hierarchy of computational compelxity which is analogous to the traditional complexity classes.

Given a digraph D, the Minimum Leaf Out-Branching problem (MinLOB) is the problem of finding in D an out-branching with the minimum possible number of leaves, i.e., vertices of out-degree 0. We describe three parameterizations of MinLOB and prove that two of them are NP-complete for every value of the parameter, but the third one is fixed-parameter tractable (FPT). The FPT parametrization is as follows: given a digraph D and a positive integral parameter k, check whether D contains an out-branching with at least k non-leaves (and find such an out-branching if it exists).

     ----------------------------------------------
Informations on future talks can be found at :
http://math.kaist.ac.kr/~sangil/seminar.php

Please email to sangil (at) kaist.edu if you wish to receive this
announcements in the future by email.