Efficient Algorithms and New Characterizations for CSP Sparsification
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912106575560704 |
|---|---|
| author | Khanna, Sanjeev Putterman, Aaron L. Sudan, Madhu |
| author_facet | Khanna, Sanjeev Putterman, Aaron L. Sudan, Madhu |
| contents | CSP sparsification, introduced by Kogan and Krauthgamer (ITCS 2015), considers the following question: how much can an instance of a constraint satisfaction problem be sparsified (by retaining a reweighted subset of the constraints) while still roughly capturing the weight of constraints satisfied by {\em every} assignment. CSP sparsification captures as a special case several well-studied problems including graph cut-sparsification, hypergraph cut-sparsification, hypergraph XOR-sparsification, and corresponds to a general class of hypergraph sparsification problems where an arbitrary $0/1$-valued {\em splitting function} is used to define the notion of cutting a hyperedge (see, for instance, Veldt-Benson-Kleinberg SIAM Review 2022). The main question here is to understand, for a given constraint predicate $P:Σ^r \to \{0,1\}$ (where variables are assigned values in $Σ$), the smallest constant $c$ such that $\widetilde{O}(n^c)$ sized sparsifiers exist for every instance of a constraint satisfaction problem over $P$. A recent work of Khanna, Putterman and Sudan (SODA 2024) [KPS24] showed {\em existence} of near-linear size sparsifiers for new classes of CSPs. In this work (1) we significantly extend the class of CSPs for which nearly linear-size sparsifications can be shown to exist while also extending the scope to settings with non-linear-sized sparsifications; (2) we give a polynomial-time algorithm to extract such sparsifications for all the problems we study including the first efficient sparsification algorithms for the problems studied in [KPS24]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_06327 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Algorithms and New Characterizations for CSP Sparsification Khanna, Sanjeev Putterman, Aaron L. Sudan, Madhu Data Structures and Algorithms CSP sparsification, introduced by Kogan and Krauthgamer (ITCS 2015), considers the following question: how much can an instance of a constraint satisfaction problem be sparsified (by retaining a reweighted subset of the constraints) while still roughly capturing the weight of constraints satisfied by {\em every} assignment. CSP sparsification captures as a special case several well-studied problems including graph cut-sparsification, hypergraph cut-sparsification, hypergraph XOR-sparsification, and corresponds to a general class of hypergraph sparsification problems where an arbitrary $0/1$-valued {\em splitting function} is used to define the notion of cutting a hyperedge (see, for instance, Veldt-Benson-Kleinberg SIAM Review 2022). The main question here is to understand, for a given constraint predicate $P:Σ^r \to \{0,1\}$ (where variables are assigned values in $Σ$), the smallest constant $c$ such that $\widetilde{O}(n^c)$ sized sparsifiers exist for every instance of a constraint satisfaction problem over $P$. A recent work of Khanna, Putterman and Sudan (SODA 2024) [KPS24] showed {\em existence} of near-linear size sparsifiers for new classes of CSPs. In this work (1) we significantly extend the class of CSPs for which nearly linear-size sparsifications can be shown to exist while also extending the scope to settings with non-linear-sized sparsifications; (2) we give a polynomial-time algorithm to extract such sparsifications for all the problems we study including the first efficient sparsification algorithms for the problems studied in [KPS24]. |
| title | Efficient Algorithms and New Characterizations for CSP Sparsification |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.06327 |