Parameterized Graph Editing with Chosen Vertex Degrees

详细信息    查看全文

• 作者：Luke Mathieson ; Stefan Szeider
• 刊名：Lecture Notes in Computer Science
• 出版年：2008
• 出版时间：2008
• 年：2008
• 卷：5165
• 期：1
• 页码：13-22
• 全文大小：424.1 KB
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

We study the parameterized complexity of the following problem: is it possible to make a given graph r-regular by applying at most k elementary editing operations; the operations are vertex deletion, edge deletion, and edge addition. We also consider more general annotated variants of this problem, where vertices and edges are assigned an integer cost and each vertex v has assigned its own desired degree δ(v) ∈ {0,...,r}. We show that both problems are fixed-parameter tractable when parameterized by (k,r), but W[1]-hard when parameterized by k alone. These results extend our earlier results on problems that are defined similarly but where edge addition is not available. We also show that if edge addition and/or deletion are the only available operations, then the problems are solvable in polynomial time. This completes the classification for all combinations of the three considered editing operations.