Reformulations and complexity of the clique interdiction problem by graph mapping

DOI10.1016/J.DAM.2021.06.008MaRDI QIDQ6558672zbMATH OpenFDO

Authors Sara Mattia

Publication date 20 June 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2021.06.008

zbMATH Keywords

bilevel programmingcomplexityedge clique interdictionfacetsmaximum cliquenode clique interdictionsingle level reformulation

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• The maximum clique interdiction problem
• A branch-and-cut algorithm for the edge interdiction clique problem
• Interdiction problems on planar graphs
• A dynamic reformulation heuristic for generalized interdiction problems
• Interdiction problems on planar graphs

Cites work

• A branch-and-cut algorithm for the maximum cardinality stable set problem
• A Characterization of Block-Graphs
• A class of algorithms for mixed-integer bilevel min-max optimization
• A fast algorithm for the maximum clique problem
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• A survey of network interdiction models and algorithms
• An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
• An exact algorithm for the maximum stable set problem
• Approximating maximum independent sets by excluding subgraphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Computing Vertex Connectivity: New Bounds from Old Techniques
• Foundations of bilevel programming
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 895368 (Why is no real title available?)
• scientific article; zbMATH DE number 956840 (Why is no real title available?)
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Minimum vertex blocker clique problem
• Reducibility among combinatorial problems
• The maximum clique interdiction problem
• The maximum clique problem
• The most vital nodes with respect to independent set and vertex cover
• The polynomial hierarchy and a simple model for competitive analysis
• Topics on perfect graphs

This page was built for publication: Reformulations and complexity of the clique interdiction problem by graph mapping

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