2013/06/11 by Cao, Yixin
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1306.2578
Given a graph G = (V,E) and a terminal s∈ V, a cut X for s is a vertex set that contains s. We look for a cut that is small in two senses, i.e., there are no more than k vertices in X and no more than t edges leaving X. Answering a question asked by Fomin et al. (arXiv:1304.6189), we show the problem is fixed-parameter tractable parameterized by either k or t.