On the parameterized complexity of non-hereditary relaxations of clique

DOI10.1016/J.TCS.2024.114625MaRDI QIDQ6549685zbMATHFDO

Authors Ambroise Baril, Antoine Castillon, Nacim Oijid

Publication date 4 June 2024

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

graphscomplexitycliqueparameterized complexityW[1-hardness]para-NP-hardness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• On the parameterized complexity of \(s\)-club cluster deletion problems
• The parameterized complexity of \(s\)-club with triangle and seed constraints
• Hardness and tractability of the \(\gamma\)-complete subgraph problem

Cites work

• An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
• An exact algorithm for the maximum \(k\)-club problem in an undirected graph
• Classifying molecular sequences using a linkage graph with their pairwise similarities
• Finding maximum subgraphs with relatively large vertex connectivity
• Fundamentals of parameterized complexity
• Hardness and tractability of the \(\gamma\)-complete subgraph problem
• Improved upper bounds for vertex cover
• Isolation concepts for efficiently enumerating dense subgraphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Listing all maximal cliques in sparse graphs in near-optimal time
• Multivariate algorithmics for finding cohesive subnetworks
• Novel approaches for analyzing biological networks
• On the maximum quasi-clique problem
• Parameterized complexity of finding subgraphs with hereditary properties.
• Parameterized computational complexity of finding small-diameter subgraphs
• Reducibility among combinatorial problems
• The node-deletion problem for hereditary properties is NP-complete

This page was built for publication: On the parameterized complexity of non-hereditary relaxations of clique

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6549685)