{"corpus_id":3046746,"paper_sha":"d6a029e0407403abf90056a4ffeb7085ca329bbe","doi":"10.4230/LIPIcs.MFCS.2016.7","arxiv_id":"1605.01866","pmid":null,"pmcid":null,"mag_id":2345492845,"dblp_id":"journals/corr/AmiriKMR16","acl_id":null,"title":"Routing with Congestion in Acyclic Digraphs","year":2016,"publication_date":"2016-05-01","venue":"International Symposium on Mathematical Foundations of Computer Science","journal":{"name":"ArXiv","pages":null,"volume":"abs/1605.01866"},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle","Conference"],"pubmed_pub_types":null,"s2_fields_of_study":["Mathematics","Computer Science"],"reference_count":29,"citation_count":16,"influential_citation_count":3,"is_open_access":true,"arxiv_categories":["cs.DS"],"arxiv_license":"http://arxiv.org/licenses/nonexclusive-distrib/1.0/","arxiv_journal_ref":null,"mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":"https://drops.dagstuhl.de/storage/00lipics/lipics-vol058-mfcs2016/LIPIcs.MFCS.2016.7/LIPIcs.MFCS.2016.7.pdf","s2_open_access_landing_url":"https://www.semanticscholar.org/paper/d6a029e0407403abf90056a4ffeb7085ca329bbe","s2_open_access_license":"CCBY","s2_open_access_status":"GREEN","pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"We study the version of the $k$-disjoint paths problem where $k$ demand pairs $(s_1,t_1)$, $\\dots$, $(s_k,t_k)$ are specified in the input and the paths in the solution are allowed to intersect, but such that no vertex is on more than $c$ paths. We show that on directed acyclic graphs the problem is solvable in time $n^{O(d)}$ if we allow congestion $k-d$ for $k$ paths. Furthermore, we show that, under a suitable complexity theoretic assumption, the problem cannot be solved in time $f(k)n^{o(d/\\log d)}$ for any computable function $f$.","claims":[{"public_id":"cl_d0db8b96a9d2dd7fdf9aa6b0965bee39","status":"active","text":"On directed acyclic graphs, the routing-with-congestion version of the k-disjoint paths problem is solvable in time n^{O(d)} when k paths are allowed congestion k-d.","confidence":0.98,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_d0db8b96a9d2dd7fdf9aa6b0965bee39"},{"public_id":"cl_0017f1ba2509a2978c4d2e2ce414d546","status":"active","text":"Under a suitable complexity-theoretic assumption, the problem has no algorithm with running time f(k)n^{o(d/log d)} for any computable function f.","confidence":0.95,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_0017f1ba2509a2978c4d2e2ce414d546"}],"concepts":[{"public_id":"co_0ed2086bc7799eafd137b7cbcccc6dfd","status":"active","name":"computable function f","description":"An arbitrary function of k that is required in the stated lower-bound form.","types":["function"],"aliases":["f"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_0ed2086bc7799eafd137b7cbcccc6dfd"},{"public_id":"co_5897a1663a016176a76aefcb3b1b5e9b","status":"active","name":"congestion k-d","description":"A congestion bound permitting each vertex to lie on at most k-d paths when routing k pairs.","types":["parameter"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_5897a1663a016176a76aefcb3b1b5e9b"},{"public_id":"co_6153508676952de4215e509387ecc719","status":"active","name":"congestion","description":"The maximum number of paths that any vertex is allowed to lie on in a routed solution.","types":["constraint"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_6153508676952de4215e509387ecc719"},{"public_id":"co_7ea6b540c73663783ac6d72d01023a30","status":"active","name":"demand pairs","description":"Input pairs of terminals (s_i, t_i) that specify which sources must be connected to which targets.","types":["input specification"],"aliases":["source-target pairs"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_7ea6b540c73663783ac6d72d01023a30"},{"public_id":"co_ad1f1a7908d11c89b21cd2d6b7d8d7e8","status":"active","name":"complexity-theoretic assumption","description":"An assumed hardness condition used to prove the lower bound.","types":["assumption"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_ad1f1a7908d11c89b21cd2d6b7d8d7e8"},{"public_id":"co_b46ff2509b9df5cada2c18cb5524924a","status":"active","name":"routing with congestion","description":"A variant of the disjoint paths problem in which paths may intersect, but each vertex may be used by only a bounded number of paths.","types":["problem variant"],"aliases":["congested routing"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_b46ff2509b9df5cada2c18cb5524924a"},{"public_id":"co_bc7a5cb2c7057dcfefe6b7be6ca9933c","status":"active","name":"k-disjoint paths problem","description":"A routing problem in which k specified source-target demand pairs must be connected by paths in a graph.","types":["problem"],"aliases":["disjoint paths problem"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_bc7a5cb2c7057dcfefe6b7be6ca9933c"},{"public_id":"co_c5c5bb14a801d8e684309e71d13ac0f3","status":"active","name":"directed acyclic graphs","description":"Directed graphs with no directed cycles, used here as the graph class for the routing problem.","types":["graph class"],"aliases":["DAGs"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_c5c5bb14a801d8e684309e71d13ac0f3"},{"public_id":"co_cdd2ef2b28f9935833ba7ae8f3749cc7","status":"active","name":"n^{O(d)}","description":"A running-time upper bound that is polynomial in n with exponent depending on d.","types":["time complexity"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_cdd2ef2b28f9935833ba7ae8f3749cc7"},{"public_id":"co_d545771e92c20a3064a52d0a0d044188","status":"active","name":"f(k)n^{o(d/log d)}","description":"A forbidden running-time form combining an arbitrary computable function of k with a subpolynomial factor in n relative to d/log d.","types":["time complexity"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_d545771e92c20a3064a52d0a0d044188"}],"external_ids":{"DOI":"10.4230/LIPIcs.MFCS.2016.7","ArXiv":"1605.01866","PubMed":null,"PubMedCentral":null,"MAG":2345492845,"DBLP":"journals/corr/AmiriKMR16","ACL":null},"open_access":{"is_open_access":true,"pdf_url":"https://drops.dagstuhl.de/storage/00lipics/lipics-vol058-mfcs2016/LIPIcs.MFCS.2016.7/LIPIcs.MFCS.2016.7.pdf","landing_url":"https://www.semanticscholar.org/paper/d6a029e0407403abf90056a4ffeb7085ca329bbe","source":"semantic_scholar","pdf_url_source":"semantic_scholar_open_access_pdf","license":"CCBY","status":"GREEN","reason":null},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":true,"full_text_source":"arxiv","count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":634803,"paper_uid":"41497103-40e5-41e3-ad83-ce0f869e6ff4","canonical_identity":{"paper_id":634803,"paper_uid":"41497103-40e5-41e3-ad83-ce0f869e6ff4","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/3046746"}