{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,6,26]],"date-time":"2022-06-26T06:06:08Z","timestamp":1656223568570},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2009,7,9]],"date-time":"2009-07-09T00:00:00Z","timestamp":1247097600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>Let <jats:italic>c<\/jats:italic>(<jats:italic>G<\/jats:italic>) be the smallest number of edges we have to test in order to determine an unknown acyclic orientation of the given graph <jats:italic>G<\/jats:italic> in the worst case. For example, if <jats:italic>G<\/jats:italic> is the complete graph on <jats:italic>n<\/jats:italic> vertices, then <jats:italic>c<\/jats:italic>(<jats:italic>G<\/jats:italic>) is the smallest number of comparisons needed to sort <jats:italic>n<\/jats:italic> numbers.<\/jats:p><jats:p>We prove that <jats:italic>c<\/jats:italic>(<jats:italic>G<\/jats:italic>) \u2264 (1\/4 + <jats:italic>o<\/jats:italic>(1))<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup> for any graph <jats:italic>G<\/jats:italic> on <jats:italic>n<\/jats:italic> vertices, answering in the affirmative a question of Aigner, Triesch and Tuza [<jats:italic>Discrete Mathematics<\/jats:italic><jats:bold>144<\/jats:bold> (1995) 3\u201310]. Also, we show that, for every \u03f5 &gt; 0, it is NP-hard to approximate the parameter <jats:italic>c<\/jats:italic>(<jats:italic>G<\/jats:italic>) within a multiplicative factor 74\/73 \u2212 \u03f5.<\/jats:p>","DOI":"10.1017\/s0963548309990289","type":"journal-article","created":{"date-parts":[[2009,7,9]],"date-time":"2009-07-09T06:51:52Z","timestamp":1247122312000},"page":"121-131","source":"Crossref","is-referenced-by-count":4,"title":["Finding an Unknown Acyclic Orientation of a Given Graph"],"prefix":"10.1017","volume":"19","author":[{"given":"OLEG","family":"PIKHURKO","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,7,9]]},"reference":[{"key":"S0963548309990289_ref14","unstructured":"[14] Jiang T. (2008) Personal communication."},{"key":"S0963548309990289_ref29","unstructured":"[29] Tuza Z. (2001) Unsolved combinatorial problems. BRICS Lecture Series, LS-01-1. Available from: http:\/\/www.brics.dk\/publications\/."},{"key":"S0963548309990289_ref24","first-page":"279","volume-title":"Theory of Graphs","author":"Simonovits","year":"1968"},{"key":"S0963548309990289_ref22","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1100-7"},{"key":"S0963548309990289_ref23","first-page":"939","volume-title":"Combinatorics II","author":"Ruzsa","year":"1978"},{"key":"S0963548309990289_ref20","first-page":"283","article-title":"On a problem of Tur\u00e1n","volume":"7","author":"Moon","year":"1962","journal-title":"Publ. Math. Inst. Hungar. Acad. Sci."},{"key":"S0963548309990289_ref27","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797328847"},{"key":"S0963548309990289_ref18","doi-asserted-by":"publisher","DOI":"10.1137\/0213008"},{"key":"S0963548309990289_ref15","volume-title":"The Art of Computer Programming, Vol. 3: Sorting and Searching","author":"Knuth","year":"1973"},{"key":"S0963548309990289_ref9","doi-asserted-by":"publisher","DOI":"10.2307\/2308750"},{"key":"S0963548309990289_ref6","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177729330"},{"key":"S0963548309990289_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"S0963548309990289_ref12","doi-asserted-by":"crossref","unstructured":"[12] H\u00e5stad J. (1999) Some optimal inapproximability results. In Proc. 29th ACM Symposium on Theory of Computing (El Paso 1997), pp. 1\u201310. ACM, New York.","DOI":"10.1145\/258533.258536"},{"key":"S0963548309990289_ref3","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060213"},{"key":"S0963548309990289_ref8","unstructured":"[8] Erd\u0151s P. (1967) Some recent results on extremal problems in graph theory: Results. In Theory of Graphs (Rome 1966), Gordon and Breach, New York; pp. 117\u2013123 (English); pp. 124\u2013130 (French)."},{"key":"S0963548309990289_ref21","first-page":"785","volume-title":"Proc. 10th Annual European Symposium on Algorithms","author":"Peczarski","year":"2002"},{"key":"S0963548309990289_ref28","first-page":"436","article-title":"On an extremal problem in graph theory (in Hungarian)","volume":"48","author":"Tur\u00e1n","year":"1941","journal-title":"Mat. Fiz. Lapok"},{"key":"S0963548309990289_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/BF02761857"},{"key":"S0963548309990289_ref13","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"S0963548309990289_ref25","first-page":"309","volume-title":"Proc. Colloq. Int. CNRS","author":"Szemer\u00e9di","year":"1976"},{"key":"S0963548309990289_ref30","doi-asserted-by":"publisher","DOI":"10.1137\/0204030"},{"key":"S0963548309990289_ref7","volume-title":"Graph Theory","author":"Diestel","year":"2006"},{"key":"S0963548309990289_ref19","first-page":"60","article-title":"Problem 28","volume":"10","author":"Mantel","year":"1907","journal-title":"Winkundige Opgaven"},{"key":"S0963548309990289_ref26","first-page":"617","volume-title":"Proc. 37th Annual Symposium on Foundations of Computer Science","author":"Trevisan","year":"1996"},{"key":"S0963548309990289_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)00281-M"},{"key":"S0963548309990289_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00040-0"},{"key":"S0963548309990289_ref1","volume-title":"Combinatorial Search","author":"Aigner","year":"1988"},{"key":"S0963548309990289_ref11","doi-asserted-by":"publisher","DOI":"10.1137\/0210034"},{"key":"S0963548309990289_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32439-3_10"},{"key":"S0963548309990289_ref17","first-page":"220","volume-title":"Proc. 22nd Annual Symposium on Foundations of Computer Science","author":"Manber","year":"1981"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548309990289","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T17:04:16Z","timestamp":1556471056000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548309990289\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7,9]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["S0963548309990289"],"URL":"https:\/\/doi.org\/10.1017\/s0963548309990289","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,7,9]]}}}