KAIST Discrete Math Seminar

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).