{"ID":2825755,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.20180","arxiv_id":"2512.20180","title":"Approximation and parameterized algorithms for covering disjointness-compliable set families","abstract":"A set-family ${\\cal F}$ is disjointness-compliable if $A' \\subseteq A \\in {\\cal F}$ implies $A' \\in {\\cal F}$ or $A \\setminus A' \\in {\\cal F}$; if ${\\cal F}$ is also symmetric then ${\\cal F}$ is proper. A classic result of Goemans and Williamson [SODA 92:307-316] states that the problem of covering a proper set-family by a min-cost edge set admits approximation ratio $2$, by a classic primal-dual algorithm. However, there are several famous algorithmic problems whose set-family ${\\cal F}$ is disjointness-compliable but not symmetric -- among them $k$-Minimum Spanning Tree ($k$-MST), Generalized Point-to-Point Connection (G-P2P), Group Steiner, Covering Steiner, multiroot versions of these problems, and others. We will show that any such problem admits approximation ratio $O(α\\log τ)$, where $τ$ is the number of inclusion-minimal sets in the family ${\\cal F}$ that models the problem and $α$ is the best known approximation ratio for the case when $τ=1$. This immediately implies several results, among them the following two. (i) The first deterministic polynomial time $O(\\log n)$-approximation algorithm for the G-P2P problem. Here the $τ=1$ case is the $k$-MST problem. (ii) Approximation ratio $O(\\log^4 n)$ for the multiroot version of the Covering Steiner problem, where each root has its own set of groups. Here the $τ=1$ case is the Covering Steiner problem. We also discuss the parameterized complexity of covering a disjointness-compliable family ${\\cal F}$, when parametrized by $τ$. We will show that if ${\\cal F}$ is proper then the problem is fixed parameter tractable and can be solved in time $O^*(3^τ)$. For the non-symmetric case we will show that the problem admits approximation ratio between $α$ and $α+1$ in time $O^*(3^τ)$, which is essentially the best possible.","short_abstract":"A set-family ${\\cal F}$ is disjointness-compliable if $A' \\subseteq A \\in {\\cal F}$ implies $A' \\in {\\cal F}$ or $A \\setminus A' \\in {\\cal F}$; if ${\\cal F}$ is also symmetric then ${\\cal F}$ is proper. A classic result of Goemans and Williamson [SODA 92:307-316] states that the problem of covering a proper set-family...","url_abs":"https://arxiv.org/abs/2512.20180","url_pdf":"https://arxiv.org/pdf/2512.20180v1","authors":"[\"Zeev Nutov\",\"Anael Vaknin\"]","published":"2025-12-23T09:19:15Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}