Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916265393651712 |
|---|---|
| author | Chandrasekaran, Karthekeyan Chekuri, Chandra Fiorini, Samuel Kulkarni, Shubhang Weltge, Stefan |
| author_facet | Chandrasekaran, Karthekeyan Chekuri, Chandra Fiorini, Samuel Kulkarni, Shubhang Weltge, Stefan |
| contents | We consider the feedback vertex set problem in undirected graphs (FVS). The input to FVS is an undirected graph $G=(V,E)$ with non-negative vertex costs. The goal is to find a minimum cost subset of vertices $S \subseteq V$ such that $G-S$ is acyclic. FVS is a well-known NP-hard problem and does not admit a $(2-ε)$-approximation for any fixed $ε> 0$ assuming the Unique Games Conjecture. There are combinatorial $2$-approximation algorithms and also primal-dual based $2$-approximations. Despite the existence of these algorithms for several decades, there is no known polynomial-time solvable LP relaxation for FVS with a provable integrality gap of at most $2$. More recent work (Chekuri and Madan, SODA '16) developed a polynomial-sized LP relaxation for a more general problem, namely Subset FVS, and showed that its integrality gap is at most $13$ for Subset FVS, and hence also for FVS.
Motivated by this gap in our knowledge, we undertake a polyhedral study of FVS and related problems. In this work, we formulate new integer linear programs (ILPs) for FVS whose LP-relaxation can be solved in polynomial time, and whose integrality gap is at most $2$. The new insights in this process also enable us to prove that the formulation in (Chekuri and Madan, SODA '16) has an integrality gap of at most $2$ for FVS. Our results for FVS are inspired by new formulations and polyhedral results for the closely-related pseudoforest deletion set problem (PFDS). Our formulations for PFDS are in turn inspired by a connection to the densest subgraph problem. We also conjecture an extreme point property for a LP-relaxation for FVS, and give evidence for the conjecture via a corresponding result for PFDS. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_12850 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set Chandrasekaran, Karthekeyan Chekuri, Chandra Fiorini, Samuel Kulkarni, Shubhang Weltge, Stefan Data Structures and Algorithms We consider the feedback vertex set problem in undirected graphs (FVS). The input to FVS is an undirected graph $G=(V,E)$ with non-negative vertex costs. The goal is to find a minimum cost subset of vertices $S \subseteq V$ such that $G-S$ is acyclic. FVS is a well-known NP-hard problem and does not admit a $(2-ε)$-approximation for any fixed $ε> 0$ assuming the Unique Games Conjecture. There are combinatorial $2$-approximation algorithms and also primal-dual based $2$-approximations. Despite the existence of these algorithms for several decades, there is no known polynomial-time solvable LP relaxation for FVS with a provable integrality gap of at most $2$. More recent work (Chekuri and Madan, SODA '16) developed a polynomial-sized LP relaxation for a more general problem, namely Subset FVS, and showed that its integrality gap is at most $13$ for Subset FVS, and hence also for FVS. Motivated by this gap in our knowledge, we undertake a polyhedral study of FVS and related problems. In this work, we formulate new integer linear programs (ILPs) for FVS whose LP-relaxation can be solved in polynomial time, and whose integrality gap is at most $2$. The new insights in this process also enable us to prove that the formulation in (Chekuri and Madan, SODA '16) has an integrality gap of at most $2$ for FVS. Our results for FVS are inspired by new formulations and polyhedral results for the closely-related pseudoforest deletion set problem (PFDS). Our formulations for PFDS are in turn inspired by a connection to the densest subgraph problem. We also conjecture an extreme point property for a LP-relaxation for FVS, and give evidence for the conjecture via a corresponding result for PFDS. |
| title | Polyhedral Aspects of Feedback Vertex Set and Pseudoforest Deletion Set |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2303.12850 |