Equivalent spectral theory for fundamental graph cut problems
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917208403214336 |
|---|---|
| author | Shao, Sihong Yang, Chuan Zhang, Dong Zhang, Weixi |
| author_facet | Shao, Sihong Yang, Chuan Zhang, Dong Zhang, Weixi |
| contents | We introduce and develop equivalent spectral graph theory for several fundamental graph cut problems including maxcut, mincut, Cheeger cut, anti-Cheeger cut, dual Cheeger problem and their useful variants. A specified strategy for achieving an equivalent eigenproblem is proposed for a general graph cut problem via the set-pair Lovász extension and the Dinkelbach scheme. For a class of 2-cut and 3-cut problems, we reveal the intrinsic difference-of-submodularity for the fractional formulations and show that their set-pair Lovász extensions yield equivalent difference-of-convex structures. Building on the Dinkelbach scheme, we finally establish a unified research roadmap for nonlinear spectral theory that provides a one-to-one correspondence between certain eigenpairs and the optimal graph cut problems. The finer structure of the eigenvectors, the Courant nodal domain theorem and the graphic feature of eigenvalues are studied systematically in the setting of these new nonlinear eigenproblems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_11077 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Equivalent spectral theory for fundamental graph cut problems Shao, Sihong Yang, Chuan Zhang, Dong Zhang, Weixi Combinatorics Spectral Theory We introduce and develop equivalent spectral graph theory for several fundamental graph cut problems including maxcut, mincut, Cheeger cut, anti-Cheeger cut, dual Cheeger problem and their useful variants. A specified strategy for achieving an equivalent eigenproblem is proposed for a general graph cut problem via the set-pair Lovász extension and the Dinkelbach scheme. For a class of 2-cut and 3-cut problems, we reveal the intrinsic difference-of-submodularity for the fractional formulations and show that their set-pair Lovász extensions yield equivalent difference-of-convex structures. Building on the Dinkelbach scheme, we finally establish a unified research roadmap for nonlinear spectral theory that provides a one-to-one correspondence between certain eigenpairs and the optimal graph cut problems. The finer structure of the eigenvectors, the Courant nodal domain theorem and the graphic feature of eigenvalues are studied systematically in the setting of these new nonlinear eigenproblems. |
| title | Equivalent spectral theory for fundamental graph cut problems |
| topic | Combinatorics Spectral Theory |
| url | https://arxiv.org/abs/2411.11077 |