Polyhedral properties of the induced cluster subgraphs

DOI10.1016/J.DAM.2021.02.040MaRDI QIDQ2022509zbMATH OpenOpenAlexFDO

Authors Seyedmohammadhossein Hosseinian, Sergiy Butenko

Publication date 29 April 2021

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

Full work available at URL https://arxiv.org/abs/1904.12025

zbMATH Keywords

cluster subgraphsindependent union of cliquesinteger programmingnetwork clustering

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Abstract: A cluster graph is a graph whose every connected component is a complete graph. Given a simple undirected graph $G$, a subset of vertices inducing a cluster graph is called an independent union of cliques (IUC), and the IUC polytope associated with $G$ is defined as the convex hull of the incidence vectors of all IUCs in the graph. The {sc Maximum IUC} problem, which is to find a maximum-cardinality IUC in a graph, finds applications in network-based data analysis. In this paper, we derive several families of facet-defining valid inequalities for the IUC polytope. We also give a complete description of this polytope for some special classes of graphs. We establish computational complexity of the separation problem for most of the considered families of valid inequalities and explore the effectiveness of employing the corresponding cutting planes in an integer (linear) programming framework for the {sc Maximum IUC} problem through computational experiments.

Recommendations

• The maximum independent union of cliques problem: complexity and exact approaches
• Facet-defining inequalities for the simple graph partitioning polytope
• On the 2-club polytope of graphs
• Combinatorial properties and further facets of maximum edge subgraph polytopes
• Polyhedral results for the bipartite induced subgraph problem

Cites work

• A class of facet producing graphs for vertex packing polyhedra
• A fast branching algorithm for cluster vertex deletion
• A faster algorithm to recognize even-hole-free graphs
• A golden ratio parameterized algorithm for cluster editing
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A more relaxed model for graph-based data clustering: s-plex cluster editing
• A polyhedral study of the generalized vertex packing problem
• A review on algorithms for maximum clique problems
• Algorithms for the generalized independent set problem based on a quadratic optimization approach
• Approximation and tidying -- a problem kernel for s-plex cluster vertex deletion
• Automated generation of search tree algorithms for hard graphs modification problems
• Cluster editing
• Cluster editing with locally bounded modifications
• Cluster graph modification problems
• Convex optimization for the planted \(k\)-disjoint-clique problem
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Detecting an Odd Hole
• Efficient algorithms for cluster editing
• Even-hole-free graphs part II: Recognition algorithm
• Fixed-parameter algorithms for cluster vertex deletion
• Geometric algorithms and combinatorial optimization.
• Graph clustering
• scientific article; zbMATH DE number 6118217 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1354124 (Why is no real title available?)
• scientific article; zbMATH DE number 2068068 (Why is no real title available?)
• scientific article; zbMATH DE number 1416629 (Why is no real title available?)
• Iterative compression and exact algorithms
• Lifting the facets of zero–one polytopes
• Node-Deletion NP-Complete Problems
• On a polynomial fractional formulation for independence number of a graph
• On clique relaxation models in network analysis
• On the complexity of testing for odd holes and induced odd paths
• On the facial structure of set packing polyhedra
• Properties of vertex packing and independence system polyhedra
• Recognizing Berge graphs
• Reducibility among combinatorial problems
• Spectral methods for graph clustering - a survey
• Subquadratic kernels for implicit 3-hitting set and 3-set packing problems
• Technical Note—A Note on Zero-One Programming
• Technical Note—Facets and Strong Valid Inequalities for Integer Programs
• The Cluster Editing Problem: Implementations and Experiments
• The disjoint cliques problem
• The generalized independent set problem: polyhedral analysis and solution approaches
• The maximum independent union of cliques problem: complexity and exact approaches
• The maximum number of induced open triangles in graphs of a given order
• The node-deletion problem for hereditary properties is NP-complete
• The strong perfect graph theorem
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• Vertex packings: Structural properties and algorithms

Cited in

(5)

• An improved approximation for maximum \(k\)-dependent set on bipartite graphs
• The maximum independent union of cliques problem: complexity and exact approaches
• A tight approximation algorithm for the cluster vertex deletion problem
• A tight approximation algorithm for the cluster vertex deletion problem
• Learning driven three-phase search for the maximum independent union of cliques problem

This page was built for publication: Polyhedral properties of the induced cluster subgraphs

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