Back
1-s2.0-s0304397525006437-main
Journal article

Finding proportionally dense subgraphs of maximum size in degree-constrained graphs

BP2-STS

  • 2026
Published in:
  • Theoretical Computer Science. - Elsevier B.V.. - 2026, vol. 1065, p. 115706
Communities
Dense subgraph
Parameterized complexity
Treewidth
Planar graphs
Complexity
Algorithms
English A proportionally dense subgraph (PDS) of a graph is an induced subgraph of size at least two such that every vertex in the subgraph has proportionally as many neighbors inside as outside of the subgraph. Then, MaxPDS is the problem of determining a PDS of maximum size in a given graph. If we further require that a PDS induces a connected subgraph, we refer to such a problem as connected MaxPDS. In this paper, motivated by the known NP-hardness result, we initiate a parameterized complexity analysis of the problem. We consider different parameters, including those related to vertex degrees in a graph and its complement. In particular, the maximum degree Δ, the ℎ-index, and the degeneracy degen . We show that MaxPDS is NP-hard parameterized by Δ, ℎ and degen . More specifically, we show that MaxPDS is NP-hard on bipartite graphs with Δ = 4, ℎ = 4 and degen = 2. Then, we show that the problem is NP-hard on dense graphs, more specifically, graphs 𝐺 such that Δ(𝐺) = 6 and 𝐺 is planar, where 𝐺 represents the complement of 𝐺. We also show that MaxPDS is NP-hard on 𝐺 such that degen(𝐺) = 2 and 𝐺 is bipartite. Finally, we show that the problem remains NP-hard on graphs 𝐺 such that 𝐺 is planar and degen (𝐺) = 2. In contrast, we show that MaxPDS is FPT parameterized by Δ + tw, where tw denotes the treewidth of the input graph. This algorithm implies that the problem is polynomial-time solvable on graphs with degen ≤ 1. Moreover, the result implies that MaxPDS is polynomial-time solvable on graphs with ℎ ≤ 2 and graphs 𝐺 such that ℎ(𝐺) ≤ 2. We extend each result presented in this paper to connected MaxPDS.
Faculty
Faculté des sciences et de médecine
Department
Département d'informatique
Language
  • English
Classification
Medicine, Technology, Engineering
License
CC BY
Open access status
hybrid
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/334190
Statistics
Document views: 10 File downloads:
  • 1-s2.0-s0304397525006437-main: 7