Tree-edges deletion problems with bounded diameter obstruction sets |
| |
Authors: | Dekel Tsur |
| |
Institution: | Department of Computer Science, Ben-Gurion University of the Negev, Israel |
| |
Abstract: | We study the following problem: given a tree G and a finite set of trees H, find a subset O of the edges of G such that G-O does not contain a subtree isomorphic to a tree from H, and O has minimum cardinality. We give sharp boundaries on the tractability of this problem: the problem is polynomial when all the trees in H have diameter at most 5, while it is NP-hard when all the trees in H have diameter at most 6. We also show that the problem is polynomial when every tree in H has at most one vertex with degree more than 2, while it is NP-hard when the trees in H can have two such vertices.The polynomial-time algorithms use a variation of a known technique for solving graph problems. While the standard technique is based on defining an equivalence relation on graphs, we define a quasiorder. This new variation might be useful for giving more efficient algorithm for other graph problems. |
| |
Keywords: | Graph algorithms Subgraph isomorphism |
本文献已被 ScienceDirect 等数据库收录! |
|