{"id":691,"date":"2025-08-28T14:11:28","date_gmt":"2025-08-28T18:11:28","guid":{"rendered":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/?p=691"},"modified":"2025-09-17T16:09:26","modified_gmt":"2025-09-17T19:09:26","slug":"two-edge-connectivity-via-pac-man-gluing","status":"publish","type":"post","link":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/2025\/08\/two-edge-connectivity-via-pac-man-gluing\/","title":{"rendered":"Two-Edge Connectivity via Pac-Man Gluing"},"content":{"rendered":"

Speaker: Felix Hommelsheim
\nCentro de Modelamiento Matematico
\nDate: Monday, September 1, 2025 at 2:30 p.m. Santiago time<\/h3>\n

Abstract:\u00a0\u00a0<\/strong><\/p>\n

We study the 2-edge-connected spanning subgraph (2-ECSS) problem: Given a graph $G$, compute a connected subgraph $H$ of $G$ with the minimum number of edges such that $H$ is spanning, i.e., $V(H) = V(G)$, and $H$ is 2-edge-connected, i.e., $H$ remains connected upon the deletion of any single edge, if such an $H$ exists. The $2$-ECSS problem is known to be NP-hard. In this work, we provide a polynomial-time $(\\frac 5 4 + \\varepsilon)$-approximation for the problem for an arbitrarily small $\\varepsilon>0$, improving the previous best approximation ratio of $\\frac{13}{10}+\\varepsilon$.<\/p>\n

Our improvement is based on two main innovations: First, we reduce solving the problem on general graphs to solving it on structured graphs with high vertex connectivity. This high vertex connectivity ensures the existence of a 4-matching across any bipartition of the vertex set with at least 10 vertices in each part. Second, we exploit this property in a later gluing step, where isolated 2-edge connected components need to be merged without adding too many edges. Using the 4-matching property, we can repeatedly glue a huge component (containing at least 10 vertices) to other components. This step is reminiscent of the Pac-Man game, where a Pac-Man (a huge component) consumes all the dots (other components) as it moves through a maze. These two innovations lead to a significantly simpler algorithm and analysis for the gluing step compared to the previous best approximation algorithm, which required a long and tedious case analysis.<\/p>\n

Venue:<\/strong> John Von Neumann Seminar Room, CMM, Beauchef 851, North Tower, 7th Floor<\/p>\n

<\/div>\n
<\/div>\n","protected":false},"excerpt":{"rendered":"

Felix Hommelsheim<\/p>\n","protected":false},"author":129,"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-691","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\/691","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\/129"}],"replies":[{"embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/comments?post=691"}],"version-history":[{"count":4,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/posts\/691\/revisions"}],"predecessor-version":[{"id":695,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/posts\/691\/revisions\/695"}],"wp:attachment":[{"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/media?parent=691"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/categories?post=691"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/eventos.cmm.uchile.cl\/postdocseminars\/wp-json\/wp\/v2\/tags?post=691"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}