TY - JOUR
T1 - Computing densest k-subgraph with structural parameters
AU - Hanaka, Tesshu
N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2023/1
Y1 - 2023/1
N2 - Densestk-Subgraph is the problem to find a vertex subset S of size k such that the number of edges in the subgraph induced by S is maximized. In this paper, we show that Densestk-Subgraph is fixed parameter tractable when parameterized by neighborhood diversity, block deletion number, distance-hereditary deletion number, and cograph deletion number, respectively. Furthermore, we give a 2-approximation 2 tc(G)/2nO(1)-time algorithm where tc(G) is the twin cover number of an input graph G.
AB - Densestk-Subgraph is the problem to find a vertex subset S of size k such that the number of edges in the subgraph induced by S is maximized. In this paper, we show that Densestk-Subgraph is fixed parameter tractable when parameterized by neighborhood diversity, block deletion number, distance-hereditary deletion number, and cograph deletion number, respectively. Furthermore, we give a 2-approximation 2 tc(G)/2nO(1)-time algorithm where tc(G) is the twin cover number of an input graph G.
KW - Approximation algorithm
KW - Densest subgraphs
KW - Fixed parameter tractability
KW - Sparsest subgraphs
KW - Structural parameters
UR - http://www.scopus.com/inward/record.url?scp=85144620791&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85144620791&partnerID=8YFLogxK
U2 - 10.1007/s10878-022-00927-1
DO - 10.1007/s10878-022-00927-1
M3 - Article
AN - SCOPUS:85144620791
SN - 1382-6905
VL - 45
JO - Journal of Combinatorial Optimization
JF - Journal of Combinatorial Optimization
IS - 1
M1 - 39
ER -