Sökning: id:"swepub:oai:lup.lub.lu.se:8b7e597d-4762-493d-82a1-d47792a53120" >
Counting thin subgr...
Counting thin subgraphs via packings faster than meet-in-the-middle time
-
- Björklund, Andreas (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
- Kaski, Petteri (författare)
- Aalto University,Helsinki Institute for Information Technology HIIT
-
- Kowalik, Lukasz (författare)
- University of Warsaw
-
(creator_code:org_t)
- 2017-09-19
- 2017
- Engelska.
-
Ingår i: ACM Transactions on Algorithms. - : Association for Computing Machinery (ACM). - 1549-6325 .- 1549-6333. ; 13:4
- Relaterad länk:
-
http://dx.doi.org/10...
-
visa fler...
-
http://arxiv.org/pdf...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- Vassilevska and Williams (STOC'09) showed how to count simple paths on k vertices and matchings on k/2 edges in ann-vertex graph in time nk/2+O(1). In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP'09), and Bjorklund et al. (ESA'09), via nst/2+O(1)-time algorithms for counting t-tuples of pairwise disjoint sets drawn from a given family of s-sized subsets of an n-element universe. Shortly afterwards, Alon and Gutner (TALG'10) showed that these problems have O(n st/2) and O(nk/2) lower bounds when counting by color coding. Here, we show that one can do better-we show that the "meet-in-the-middle" exponent st/2 can be beaten and give an algorithm that counts in time n0.45470382st+O(1) for t a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on k vertices and pathwidth pk in an n-vertex graph in n0.45470382k+2p+O(1) time, improving on the three mentioned algorithms for paths and matchings, and circumventing the color-coding lower bound. We also give improved bounds for counting t-tuples of disjoint s-sets for s = 2, 3, 4. Our algorithms use fast matrix multiplication. We show an argument that this is necessary to go below the meet-in-the-middle barrier.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Counting low pathwidth graphs
- Counting matchings
- Counting packings
- Counting paths
- FPT algorithms
- Matrix multiplication
- Meet in the middle
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas