{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:08:14Z","timestamp":1750306094437,"version":"3.41.0"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2017,5,12]],"date-time":"2017-05-12T00:00:00Z","timestamp":1494547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2017,6,30]]},"abstract":"\n For a graph\n G<\/jats:italic>\n (\n V<\/jats:italic>\n ,\n E<\/jats:italic>\n ) (|\n V<\/jats:italic>\n | =\n n<\/jats:italic>\n ) and a vertex\n s<\/jats:italic>\n \u2208\n V<\/jats:italic>\n , a weighting scheme (\n W<\/jats:italic>\n :\n E<\/jats:italic>\n \u21a6 Z\n +<\/jats:sup>\n ) is called a\n min-unique<\/jats:italic>\n (resp.\n max-unique<\/jats:italic>\n ) weighting scheme if, for any vertex\n v<\/jats:italic>\n of the graph\n G<\/jats:italic>\n , there is a unique path of minimum (resp. maximum) weight from\n s<\/jats:italic>\n to\n v<\/jats:italic>\n , where weight of a path is the sum of the weights assigned to the edges. Instead, if the number of paths of minimum (resp. maximum) weight is bounded by\n \n n\n c<\/jats:sup>\n <\/jats:italic>\n for some constant\n c<\/jats:italic>\n , then the weighting scheme is called a\n min-poly<\/jats:italic>\n (resp.\n max-poly<\/jats:italic>\n ) weighting scheme.\n <\/jats:p>\n \n In this article, we propose an unambiguous nondeterministic log-space (UL) algorithm for the problem of testing reachability graphs augmented with a\n min-poly<\/jats:italic>\n weighting scheme. This improves the result in Reinhardt and Allender [2000], in which a UL algorithm was given for the case when the weighting scheme is\n min-unique<\/jats:italic>\n .\n <\/jats:p>\n Our main technique involves triple inductive counting and generalizes the techniques of Immerman [1988], Szelepcs\u00e9nyi [1988], and Reinhardt and Allender [2000], combined with a hashing technique due to Fredman et al. [1984] (also used in Garvin et al. [2014]). We combine this with a complementary unambiguous verification method to give the desired UL algorithm.<\/jats:p>\n \n At the other end of the spectrum, we propose a UL algorithm for testing reachability in layered DAGs augmented with\n max-poly<\/jats:italic>\n weighting schemes. To achieve this, we first reduce reachability in layered DAGs to the longest path problem for DAGs with a unique source, such that the reduction also preserves the\n max-unique<\/jats:italic>\n and\n max-poly<\/jats:italic>\n properties of the graph. Using our techniques, we generalize the double inductive counting method in Limaye et al. [2009], in which the UL algorithm was given for the longest path problem on DAGs with a unique sink and augmented with a\n max-unique<\/jats:italic>\n weighting scheme.\n <\/jats:p>\n \n An important consequence of our results is that, to show NL = UL, it suffices to design log-space computable\n min-poly<\/jats:italic>\n (or\n max-poly<\/jats:italic>\n ) weighting schemes for layered DAGs.\n <\/jats:p>","DOI":"10.1145\/3070902","type":"journal-article","created":{"date-parts":[[2017,5,15]],"date-time":"2017-05-15T12:13:58Z","timestamp":1494850438000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Min\/Max-Poly Weighting Schemes and the NL versus UL Problem"],"prefix":"10.1145","volume":"9","author":[{"given":"Anant","family":"Dhayal","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jayalal","family":"Sarma","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saurabh","family":"Sawlani","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,5,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73001-9_3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9172-z"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"volume-title":"Graph Theory","author":"Bondy A.","key":"e_1_2_1_4_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-84628-970-5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1490270.1490274"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0050-8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217058"},{"volume-title":"Proceedings of Computing: The Australasian Theory Symposium (CATS\u201909)","year":"2009","author":"Limaye Nutan","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-012-0047-3"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060647"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798339041"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00299636"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3070902","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3070902","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:27Z","timestamp":1750217427000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3070902"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,12]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,6,30]]}},"alternative-id":["10.1145\/3070902"],"URL":"https:\/\/doi.org\/10.1145\/3070902","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2017,5,12]]},"assertion":[{"value":"2016-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}