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. In this paper, we show that MaxPDS is FPT parameterized by \(\varDelta + \operatorname {tw}\) , where \(\varDelta \) is the maximum degree and \(\operatorname {tw}\) is the treewidth of the input graph. This algorithm implies that the problem is polynomial-time solvable on graphs with \(\operatorname {degen} \le 1\) , where \(\operatorname {degen}\) represents the degeneracy. Moreover, the result implies that MaxPDS is polynomial-time solvable on graphs with \(h\le 2\) and graphs G such that \(h(\overline{G})\le 2\) , where h represents the h-index and \(\overline{G}\) is the complement of G. Given the aforementioned results, we then show that MaxPDS is NP-hard parameterized by \(\varDelta \) . More specifically, we show that MaxPDS is NP-hard on graphs with \(\varDelta =4\) , \(h=4\)  and \(\operatorname {degen}=2\) . Then, we show that MaxPDS is NP-hard on graphs G such that \(\overline{G}\) is planar and \(\varDelta (\overline{G})\le 6\) . We also show MaxPDS is NP-hard on graphs G such that \(\operatorname {degen}(\overline{G}) \le 2\) and \(\overline{G}\) is bipartite. Finally, we show that MaxPDS remains NP-hard on planar graphs.

Proportionally Dense Subgraphs: Parameterized Hardness and Efficiently Solvable Cases

会议论文
发表日期：

2025年

查看全文

Narmina Baghirova,
Antoine Castillon

摘要

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. In this paper, we show that MaxPDS is FPT parameterized by \(\varDelta + \operatorname {tw}\) , where \(\varDelta \) is the maximum degree and \(\operatorname {tw}\) is the treewidth of the input graph. This algorithm implies that the problem is polynomial-time solvable on graphs with \(\operatorname {degen} \le 1\) , where \(\operatorname {degen}\) represents the degeneracy. Moreover, the result implies that MaxPDS is polynomial-time solvable on graphs with \(h\le 2\) and graphs G such that \(h(\overline{G})\le 2\) , where h represents the h-index and \(\overline{G}\) is the complement of G. Given the aforementioned results, we then show that MaxPDS is NP-hard parameterized by \(\varDelta \) . More specifically, we show that MaxPDS is NP-hard on graphs with \(\varDelta =4\) , \(h=4\) and \(\operatorname {degen}=2\) . Then, we show that MaxPDS is NP-hard on graphs G such that \(\overline{G}\) is planar and \(\varDelta (\overline{G})\le 6\) . We also show MaxPDS is NP-hard on graphs G such that \(\operatorname {degen}(\overline{G}) \le 2\) and \(\overline{G}\) is bipartite. Finally, we show that MaxPDS remains NP-hard on planar graphs.