Back to Search
Start Over
Parameterized counting matching and packing: A family of hard problems that admit FPTRAS.
- Source :
-
Theoretical Computer Science . Jul2018, Vol. 734, p83-93. 11p. - Publication Year :
- 2018
-
Abstract
- In the field of parameterized counting complexity, the problems that are #W[1]-hard and admit fixed-parameter tractable randomized approximation scheme (FPTRAS) have attracted much attention in recent years. In this paper, we focus on the problems on parameterized counting matching and packing. These problems include counting set packing , counting matching , and counting subgraph packing (including both vertex-disjoint and edge-disjoint versions). We study the parameterized complexity on these problems. On the basis of some results for counting graph matchings, we show that a series of problems are #W[1]-hard. Furthermore, by extending the previous algorithm for counting 3- d matching , we obtain FPTRAS for each considered problem, respectively. Our results indicate that the problems on parameterized counting matching and packing form a large family of problems that are #W[1]-hard and admit FPTRAS. [ABSTRACT FROM AUTHOR]
- Subjects :
- *SUBGRAPHS
*GRAPH theory
*GEOMETRIC vertices
*GRAPHIC methods
*INTEGERS
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 734
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 129922689
- Full Text :
- https://doi.org/10.1016/j.tcs.2017.09.022