Polynomial-Time Algorithms for Submodular Laplacian Systems

2018/03/29 by Kaito Fujii, Fujii, Kaito, Tasuku Soma +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph theory and applications #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.1803.10923

openalex publication_date 2018/03/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let G=(V,E) be an undirected graph, L_G∈ ℝ^{V × V} be the associated Laplacian matrix, and b ∈ ℝ^V be a vector. Solving the Laplacian system L_G x = b has numerous applications in theoretical computer science, machine learning, and network analysis. Recently, the notion of the Laplacian operator L_F:ℝ^V → 2^ℝV for a submodular transformation F:2^V → ℝ₊^E was introduced, which can handle undirected graphs, directed graphs, hypergraphs, and joint distributions in a unified manner. In this study, we show that the submodular Laplacian system L_F( x) \ni b can be solved in polynomial time. Furthermore, we also prove that even when the submodular Laplacian system has no solution, we can solve its regression form in polynomial time. Finally, we discuss potential applications of submodular Laplacian systems in machine learning and network analysis.

Citations

• Faster generation of random spanning trees

Cited by

• On the Spectral Expansion of Monotone Subsets of the Hypercube

Related

• Cheeger Inequalities for Submodular Transformations
• On Fast Computation of Directed Graph Laplacian Pseudo-Inverse
• Subspace arrangements, graph rigidity and derandomization through submodular optimization
• Derandomization Beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space
• Hypergraph p-Laplacian equations for data interpolation and semi-supervised learning