Deletion to Induced Matching
In the DELETION TO INDUCED MATCHING problem, we are given a graph $G$ on $n$ vertices, $m$ edges and a non-negative integer $k$ and asks whether there exists a set of vertices $S \subseteq V(G) $ such that $|S|\le k$ and the size of any connected component in $G-S$ is exactly 2. In this paper, we pr...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2008.09660 http://arxiv.org/abs/2008.09660 |
| Tags: |
No Tags, Be the first to tag this record!
|
Similar Items: Deletion to Induced Matching
- Exact Algorithms for Edge Deletion to Cactus
- s-Club Cluster Vertex Deletion on Interval and Well-Partitioned Chordal Graphs
- Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
- Complexity of the (Connected) Cluster Vertex Deletion problem on $H$-free graphs
- Explicit two-deletion codes with redundancy matching the existential bound
- Vertex deletion into bipartite permutation graphs