Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Detecting fixed patterns in chordal graphs in polynomial time.

Belmonte, R. and Golovach, P.A. and Heggernes, P. and van 't Hof, P. and Kaminski, M. and Paulusma, Daniel (2014) 'Detecting fixed patterns in chordal graphs in polynomial time.', Algorithmica., 69 (3). pp. 501-521.

Abstract

The Contractibility problem takes as input two graphs G and H, and the task is to decide whether H can be obtained from G by a sequence of edge contractions. The Induced Minor and Induced Topological Minor problems are similar, but the first allows both edge contractions and vertex deletions, whereas the latter allows only vertex deletions and vertex dissolutions. All three problems are NP-complete, even for certain fixed graphs H. We show that these problems can be solved in polynomial time for every fixed H when the input graph G is chordal. Our results can be considered tight, since these problems are known to be W[1]-hard on chordal graphs when parameterized by the size of H. To solve Contractibility and Induced Minor, we define and use a generalization of the classic Disjoint Paths problem, where we require the vertices of each of the k paths to be chosen from a specified set. We prove that this variant is NP-complete even when k=2, but that it is polynomial-time solvable on chordal graphs for every fixed k. Our algorithm for Induced Topological Minor is based on another generalization of Disjoint Paths called Induced Disjoint Paths, where the vertices from different paths may no longer be adjacent. We show that this problem, which is known to be NP-complete when k=2, can be solved in polynomial time on chordal graphs even when k is part of the input. Our results fit into the general framework of graph containment problems, where the aim is to decide whether a graph can be modified into another graph by a sequence of specified graph operations. Allowing combinations of the four well-known operations edge deletion, edge contraction, vertex deletion, and vertex dissolution results in the following ten containment relations: (induced) minor, (induced) topological minor, (induced) subgraph, (induced) spanning subgraph, dissolution, and contraction. Our results, combined with existing results, settle the complexity of each of the ten corresponding containment problems on chordal graphs.

Item Type:Article
Additional Information:This work is supported by EPSRC (EP/G043434/1) and Royal Society (JP100692), and by the Research Council of Norway (197548/F20). Preliminary versions of different parts of the paper were presented at MFCS 2011 [18] and ISAAC 2011 [1].
Full text:(AM) Accepted Manuscript
Download PDF
(400Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1007/s00453-013-9748-5
Publisher statement:The final publication is available at Springer via http://dx.doi.org/10.1007/s00453-013-9748-5
Date accepted:No date available
Date deposited:17 April 2013
Date of first online publication:July 2014
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar