Golovach, P.A and Kratsch, D. and Paulusma, Daniel (2012) 'Detecting induced minors in AT-free graphs.', in Algorithms and computation : 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, 19-21 December 2012 ; proceedings. Berlin ; Heidelberg: Springer, pp. 495-505. Lecture notes in computer science., 7676 (7676).
The problem Induced Minor is to test whether a graph G can be modified into a graph H by a sequence of vertex deletions and edge contractions. We prove that Induced Minor is polynomial-time solvable when G is AT-free, and H is fixed, i.e., not part of the input. Our result can be considered to be optimal in some sense as we also prove that Induced Minor is W-hard on AT-free graphs, when parameterized by |VH|. In order to obtain it we prove that the Set-Restricted k-Disjoint Paths problem can be solved in polynomial time on AT-free graphs for any fixed k. We also use the latter result to prove that the Set-Restricted k-Disjoint Connected Subgraphs problem is polynomial-time solvable on AT-free graphs for any fixed k.
|Item Type:||Book chapter|
|Full text:||Full text not available from this repository.|
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-642-35261-4_52|
|Date accepted:||No date available|
|Date deposited:||No date available|
|Date of first online publication:||2012|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|