Closest 4-leaf power is fixed-parameter tractable

Michael Dom, Jiong Guo, Falk Hüffner, Rolf NiedermeierDiscret. Appl. Math 2008 · OpenReview

Abstract

The NP-complete Closest 4-Leaf Power problem asks, given an undirected graph, whether it can be modified by at most r<math><mi is="true">r</mi></math> edge insertions or deletions such that it becomes a 4-leaf power. Herein, a 4-leaf power is a graph that can be constructed by considering an unrooted tree—the 4-leaf root—with leaves one-to-one labeled by the graph vertices, where we connect two graph vertices by an edge iff their corresponding leaves are at distance at most 4 in the tree. Complementing previous work on Closest 2-Leaf Power and Closest 3-Leaf Power, we give the first algorithmic result for Closest 4-Leaf Power, showing that Closest 4-Leaf Power is fixed-parameter tractable with respect to the parameter r<math><mi is="true">r</mi></math>.
BibTeX
@inproceedings{dom2008closest,
  author = {Michael Dom and Jiong Guo and Falk Hüffner and Rolf Niedermeier},
  title = {{Closest 4-leaf power is fixed-parameter tractable}},
  booktitle = {Discret. Appl. Math},
  year = {2008},
  url = {https://openreview.net/forum?id=GEGSxTX9qr},
}

Loading related content...

Figure