Cutting a tree with subgraph complementation is hard, except for some small trees
type: Item
instance of: scholarly article
title: Cutting a tree with subgraph complementation is hard, except for some small trees
zbMATH Open document ID: 1546.05048
author: Dhanyamol Antony
author: Sagartanu Pal
author: R. B. Sandeep
author: R. Subashini
published in: Journal of Graph Theory
publication date: 2024-08-30T00:00:00Z
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 7903754
zbMATH Keywords: graph modification
zbMATH Keywords: paw
zbMATH Keywords: subgraph complementation
MaRDI profile type: MaRDI publication profile
cites work: Hardness of edge-modification problems
cites work: On subgraph complementation to \(H\)-free Graphs
cites work: Dichotomy Results on the Hardness of $H$-free Edge Modification Problems
cites work: Hardness of Approximation for H -free Edge Modification Problems
cites work: On generating triangle-free graphs
cites work: Subgraph complementation and minimum rank
cites work: Incompressibility of \(H\)-free edge modification problems
cites work: Cluster editing: kernelization based on edge cuts
cites work: A polynomial kernel for diamond-free editing
cites work: Q3416248
cites work: Complement reducible graphs
cites work: Parameterized Algorithms
cites work: Compressing Bounded Degree Graphs
cites work: Q6089654
cites work: The complexity of some edge deletion problems
cites work: Subgraph complementation
cites work: Transitiv orientierbare Graphen
cites work: Q4437501
cites work: Polynomial-time Algorithm for Maximum Weight Independent Set on P 6 -free Graphs
cites work: On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
cites work: A survey of the algorithmic aspects of modular decomposition
cites work: Q4814092
cites work: Recognizing \(P_ 3\)-structure: A switching approach
cites work: On perfect switching classes
cites work: On Switching to H‐Free Graphs
cites work: Recent developments on graphs of bounded clique-width
cites work: Cluster editing with locally bounded modifications
cites work: Q4027169
cites work: Two edge modification problems without polynomial kernels
cites work: Independent Set in P5-Free Graphs in Polynomial Time
cites work: Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
cites work: On maximal independent sets of vertices in claw-free graphs
cites work: Paw-free graphs
cites work: Quasi-polynomial-time algorithm for independent set in \(P_t\)-free graphs via shrinking the space of induced paths
cites work: Cluster graph modification problems
cites work: Edge-Deletion Problems
cites work: Polynomial kernels for paw-free edge modification problems
DOI: 10.1002/JGT.23112
description: scientific article; zbMATH DE number 7903754