کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
421211 | 684163 | 2012 | 12 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Edge contractions in subclasses of chordal graphs Edge contractions in subclasses of chordal graphs](/preview/png/421211.png)
Modifying a given graph to obtain another graph is a well-studied problem with applications in many fields. Given two input graphs GG and HH, the Contractibility problem is to decide whether HH can be obtained from GG by a sequence of edge contractions. This problem is known to be NP-complete already when both input graphs are trees of bounded diameter. We prove that Contractibility can be solved in polynomial time when GG is a trivially perfect graph and HH is a threshold graph, thereby giving the first classes of graphs of unbounded treewidth and unbounded degree on which the problem can be solved in polynomial time. We show that this polynomial-time result is in a sense tight, by proving that Contractibility is NP-complete when GG and HH are both trivially perfect graphs, and when GG is a split graph and HH is a threshold graph. If the graph HH is fixed and only GG is given as input, then the problem is called HH-Contractibility. This problem is known to be NP-complete on general graphs already when HH is a path on four vertices. We show that, for any fixed graph HH, the HH-Contractibility problem can be solved in polynomial time if the input graph GG is a split graph.
Journal: Discrete Applied Mathematics - Volume 160, Issues 7–8, May 2012, Pages 999–1010