Path Graph Completion

Input

Graph $G = (V, E)$, non-negative integer $K$.

Question

Is there a superset $E'$ containing $E$ such that $|E' - E| \leq K$ and the graph $G' = (V, E')$ is the intersection graph of a family of paths on an undirected tree?

Classes

• NP-complete

Comments

Corresponding problem in which $G'$ must be the intersection graph of a family of directed paths on an oriented tree (i.e. rooted, with all arcs directed away from the root) is also NP-complete.

Proofs

NP-complete

Transformation from [problem:interval-graph-completion].

Reducible from

• [interval-graph-completion]