Approximately counting paths and cycles in a graph

详细信息    查看全文

• 作者：Masaki Yamamoto ^{yamamoto@st.seikei.ac.jp}
• 关键词：Approximate counting ; #P-hard ; FPRAS ; Inapproximability
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：30 January 2017
• 年：2017
• 卷：217
• 期：part_P2
• 页码：381-387
• 全文大小：408 K
• 卷排序：217

文摘

We consider the time complexity of problems of counting paths and cycles in a graph, respectively. We first show that these two problems are #P-hard. Then, we show an inapproximability result: there is no FPRAS for approximately counting paths and cycles in a graph, respectively unless RP=NPRP=NP.