arXiv preprint ·
Claw-Free and Line Graph Edge Deletion on Block Graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Connectivity Bounds for GHZ Graphs
The Komlós Problem in Matrix-Multiplication Time
Geometric Graph Representations via Compact SAT Encodings
A Practical Combinatorial Interior Point Method for Minimum-Cost Flow
An improved randomized algorithm for finding sinks of Acyclic Unique Sink Orientations of the binary hypercube
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.