Cutting a tree with subgraph complementation is hard, except for some small trees
From MaRDI portal
Publication:6163958
DOI10.1007/978-3-031-20624-5_1arXiv2202.13620OpenAlexW4312273856MaRDI QIDQ6163958
R. Subashini, R. B. Sandeep, Dhanyamol Antony, Sagartanu Pal
Publication date: 26 July 2023
Published in: LATIN 2022: Theoretical Informatics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2202.13620
Algorithms in computer science (68Wxx) Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Cluster editing with locally bounded modifications
- Recent developments on graphs of bounded clique-width
- Hardness of edge-modification problems
- Paw-free graphs
- On maximal independent sets of vertices in claw-free graphs
- Complement reducible graphs
- Two edge modification problems without polynomial kernels
- Cluster editing: kernelization based on edge cuts
- Cluster graph modification problems
- Recognizing \(P_ 3\)-structure: A switching approach
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
- A polynomial kernel for diamond-free editing
- Subgraph complementation and minimum rank
- Subgraph complementation
- Incompressibility of \(H\)-free edge modification problems
- On subgraph complementation to \(H\)-free graphs
- Compressing Bounded Degree Graphs
- On Generating Triangle-Free Graphs
- The complexity of some edge deletion problems
- Edge-Deletion Problems
- Hardness of Approximation for H -free Edge Modification Problems
- Polynomial-time algorithm for Maximum Weight Independent Set on P6-free graphs
- Dichotomy Results on the Hardness of $H$-free Edge Modification Problems
- Independent Set in P5-Free Graphs in Polynomial Time
- On Switching to H‐Free Graphs
- Parameterized Algorithms
- Polynomial kernels for paw-free edge modification problems
- On perfect switching classes
