{"id":663,"date":"2025-03-27T13:32:36","date_gmt":"2025-03-27T16:32:36","guid":{"rendered":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/?p=663"},"modified":"2025-04-02T09:19:32","modified_gmt":"2025-04-02T12:19:32","slug":"shortest-odd-path-on-undirected-graphs-with-conservative-weights","status":"publish","type":"post","link":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/2025\/03\/shortest-odd-path-on-undirected-graphs-with-conservative-weights\/","title":{"rendered":"Shortest Odd path on undirected graphs with conservative weights"},"content":{"rendered":"<h3>Speaker:\u00a0 <a href=\"https:\/\/scholar.google.com\/citations?user=tI8FtGsAAAAJ\">Mirabel Mendoza <\/a><br \/>\nCenter for Mathematical Modeling, U. de Chile<br \/>\nDate: Monday, March 31, 2025 at 2:30 p.m. Santiago time<\/h3>\n<p style=\"text-align: left\"><strong>Abstract:\u00a0\u00a0<\/strong><\/p>\n<p>We consider the Shortest Odd Path (SOP) problem, where given an undirected graph $G$, a weight function on its edges, and two vertices $s$ and $t$ in $G$, the aim is to find an $(s,t)$-path with odd length and, among all such paths, of minimum weight. For the case when the weight function is conservative, i.e., when every cycle has non-negative total weight, the complexity of the SOP problem had been open for 20 years, and was recently shown to be NP-hard. I&#8217;ll present a polynomial-time algorithm for the special case when the weight function is conservative and the set of negative-weight edges forms a single tree. The algorithm exploits the strong connection between SOP and the problem of finding two internally vertex-disjoint paths between two terminals in an undirected edge-weighted graph. This is a joint work with Alp\u00e1r J\u00fcttner, Csaba Kir\u00e1ly, Gyula Pap, Ildik\u00f3 Schlotter, and Yutaro Yamaguchi.<\/p>\n<p><strong>Venue:<\/strong> John Von Neumann Seminar Room, CMM, Beauchef 851, North Tower, 7th Floor<\/p>\n<div class=\"notranslate\"><\/div>\n<div class=\"notranslate\"><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Mirabel Mendoza (CMM, U. de Chile)<\/p>\n","protected":false},"author":103,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false,"footnotes":""},"categories":[5],"tags":[],"class_list":["post-663","post","type-post","status-publish","format-standard","hentry","category-past-seminar"],"_links":{"self":[{"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/posts\/663","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/users\/103"}],"replies":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/comments?post=663"}],"version-history":[{"count":1,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/posts\/663\/revisions"}],"predecessor-version":[{"id":664,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/posts\/663\/revisions\/664"}],"wp:attachment":[{"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/media?parent=663"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/categories?post=663"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/tags?post=663"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}