Proportionally dense subgraph of maximum size: complexity and approximation

DOI10.1016/J.DAM.2019.07.010MaRDI QIDQ2334039zbMATH OpenOpenAlexWikidataFDO

Authors Cristina Bazgan, Janka Chlebíková, Clément Dallard, Thomas Pontoizeau

Publication date 6 November 2019

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

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

zbMATH Keywords

approximationcomplexitydense subgraphHamiltonian cubic graphs

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Eulerian and Hamiltonian graphs (05C45) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We define a proportionally dense subgraph (PDS) as an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the graph. We prove that the problem of finding a PDS of maximum size is APX-hard on split graphs, and NP-hard on bipartite graphs. We also show that deciding if a PDS is inclusion-wise maximal is co-NP-complete on bipartite graphs. Nevertheless, we present a simple polynomial-time $(2-frac2Delta+1)$-approximation algorithm for the problem, where $Delta$ is the maximum degree of the graph. Finally, we show that all Hamiltonian cubic graphs with $n$ vertices (except two) have a PDS of size $lfloorfrac2n+13floor$, which we prove to be an upper bound on the size of a PDS in cubic graphs.

Recommendations

• Graphs without a partition into two proportionally dense subgraphs
• Dense subgraph problems with output-density conditions
• Algorithms and Computation
• Finding dense subgraphs
• Constant factor approximation algorithms for the densest \(k\)-subgraph problem on proper interval graphs and bipartite permutation graphs

Cites work

• A general view on computing communities
• Almost all cubic graphs are Hamiltonian
• Complexity of approximating bounded variants of optimization problems
• Complexity of finding dense subgraphs
• Defensive k-alliances in graphs
• Finding Dense Subgraphs with Size Bounds
• Graphs without a partition into two proportionally dense subgraphs
• scientific article; zbMATH DE number 2104820 (Why is no real title available?)
• On Finding Dense Subgraphs
• Reducibility among combinatorial problems
• Structural and algorithmic properties of 2-community structures
• The dense \(k\)-subgraph problem

Cited in

(7)

• A note on the approximability of the dense subgraph problem.
• Graphs without a partition into two proportionally dense subgraphs
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Proximity Search for Maximal Subgraph Enumeration
• Dense graph partitioning on sparse and dense graphs
• Finding proportionally dense subgraphs of maximum size in degree-constrained graphs
• Proportionally dense subgraphs: parameterized hardness and efficiently solvable cases

This page was built for publication: Proportionally dense subgraph of maximum size: complexity and approximation

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