Block graph edge removal solves claw free and line graph problems equally
Claw-Free and Line Graph Edge Deletion on Block Graphs
Data Structures and AlgorithmsDiscrete Mathematics
Summary
The paper studies how to remove as few edges as possible from special networks called block graphs to achieve two properties: being claw-free and being a line graph. Since every line graph is claw-free, the authors show that the minimum edges needed to fix either problem is the same on block graphs. They develop a method that builds a special edge structure inside the blocks while preserving claw-freeness, which reduces the problem to selecting vertices using a fast algorithm. Their approach runs efficiently and also applies to related problems involving larger 'claw-like' structures.
What this means in practice
- •For network engineers: Identify minimal edge removals in block-structured networks to eliminate claw-like interaction patterns efficiently.
- •For graph algorithm developers: Incorporate linear-time dynamic programming methods to optimize edge deletions producing line or claw-free graphs in block graph inputs.
Authors
Rajat Adak
Abstract
Edge deletion problems ask for the fewest edges whose deletion gives a graph with a specified property. We study two such problems on block graphs. First making the graph claw-free, and second making it a line graph. Since every line graph is claw-free, the second problem is at least as difficult as the first. We show that on block graphs the two optimum values are always equal, and both are attained by the line graph of a forest. The main step is a completion argument, in which starting from any claw-free solution, we put back edges to get some nice structure inside each block still maintaining the claw-free property. This reduces both edge-deletion problems to the same problem of selecting vertices within the blocks of the input graph. We solve it by dynamic programming in $O(n+m)$ time, which also produces an optimal deletion set and a forest whose line graph is what remains after the completion argument. We also extend the method to $K_{1,r+1}$-free edge deletion for every fixed $r$.