Supports for Outerplanar and Bounded Treewidth Graphs

Rajiv Raman, Karamjeet Singh · 2025

Read Supports for Outerplanar and Bounded Treewidth Graphs by Rajiv Raman, Karamjeet Singh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-05039.txt.

Description

Rajiv Raman and Karamjeet Singh study sparse supports for hypergraphs built from subgraphs of a given graph, published in 2025. A support is a graph on the same points that keeps each hyperedge connected. Such supports are a key step in designing fast approximation schemes for packing and covering problems.

The authors look at primal, dual, and intersection hypergraphs made from non-piercing subgraphs, a family where each part and each difference stays connected. For outerplanar graphs, all three kinds admit outerplanar supports. For graphs of bounded treewidth, they give supports whose treewidth is bounded in terms of the original. They also show the growth in some bounds is sometimes unavoidable. All results come with polynomial-time algorithms.

Catalog record

CREATORRajiv Raman, Karamjeet Singh
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE100 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-05039

Browse the full library · About the Tower of Babel