{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T11:07:22Z","timestamp":1648552042432},"reference-count":20,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2015,6]]},"abstract":"<jats:p> We study upper and lower bounds on the vertex-kernel size for the 3-HITTING SET problem on hypergraphs of degree at most 3, denoted 3-3-HS. We first show that, unless P = NP, 3-3-HS on 3-uniform hypergraphs does not have a vertex-kernel of size at most 35k\/19 &gt; 1.8421k. We then give a 4k - k<jats:sup>0.2692<\/jats:sup> vertex-kernel for 3-3-hs that is computable in time O(k<jats:sup>2<\/jats:sup>). We do not assume that the hypergraph is 3-uniform for the vertex-kernel upper bound results. This result improves the upper bound of 4k on the vertex-kernel size for 3-3-HS, implied by the results of Wahlstr\u00f6m. <\/jats:p>","DOI":"10.1142\/s1793830915500111","type":"journal-article","created":{"date-parts":[[2015,2,6]],"date-time":"2015-02-06T01:28:58Z","timestamp":1423186138000},"page":"1550011","source":"Crossref","is-referenced-by-count":0,"title":["3-Hitting set on bounded degree hypergraphs: Upper and lower bounds on the kernel size"],"prefix":"10.1142","volume":"07","author":[{"given":"Iyad","family":"Kanj","sequence":"first","affiliation":[{"name":"School of Computing, DePaul University, 243 S. Wabash Avenue, Chicago, IL 60604, USA"}]},{"given":"Fenghui","family":"Zhang","sequence":"additional","affiliation":[{"name":"Google Kirkland, 747 6th Street South, Kirkland, WA 98033, USA"}]}],"member":"219","published-online":{"date-parts":[[2015,5,25]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.09.002"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1"},{"key":"rf3","first-page":"27","volume":"25","author":"Bar-Yehuda R.","year":"1985","journal-title":"Ann. Discrete Math."},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.04.001"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.03.004"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190150110"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1137\/050646354"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1186"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1145-7"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.06.026"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9199-6"},{"key":"rf15","first-page":"38","volume":"8","author":"Fernau H.","journal-title":"ACM Trans. Algorithms"},{"key":"rf16","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M.","year":"1979"},{"key":"rf17","first-page":"58","volume":"113","author":"Kratsch S.","year":"2014","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci. EATCS"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2013.02.001"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30891-8_10"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/S1570-8667(03)00009-1"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.09.004"},{"key":"rf23","volume-title":"Introduction to Graph Theory","author":"West D.","year":"1996"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830915500111","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T03:35:54Z","timestamp":1565148954000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830915500111"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,25]]},"references-count":20,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2015,5,25]]},"published-print":{"date-parts":[[2015,6]]}},"alternative-id":["10.1142\/S1793830915500111"],"URL":"https:\/\/doi.org\/10.1142\/s1793830915500111","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,25]]}}}