Computing densest k-subgraph with structural parameters
Computing densest k-subgraph with structural parameters
复制标题
DOI：
10.1007/s10878-022-00927-1
复制
发表时间：
2022-07
影响因子：
1
通讯作者：
T. Hanaka
中科院分区：
文献类型：
--
作者：
T. Hanaka
Densestk-Subgraphis the problem to find a vertex subsetSof sizeksuch that the number of edges in the subgraph induced bySis maximized. In this paper, we show thatDensestk-Subgraphis 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{{{\texttt{tc}}(G)}/2}n^{O(1)}$$\end{document}-time algorithm where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\texttt{tc}}(G)}$$\end{document} is the twin cover number of an input graphG.
Densestk-Subgraphis the problem to find a vertex subsetSof sizeksuch that the number of edges in the subgraph induced bySis maximized. In this paper, we show thatDensestk-Subgraphis 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{{{\texttt{tc}}(G)}/2}n^{O(1)}$$\end{document}-time algorithm where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\texttt{tc}}(G)}$$\end{document} is the twin cover number of an input graphG.