Skip to content
DraconiticResearch
Search Sources API
203,948 studies31 sourcesUpdated 21 min ago
PreprintarXiv licencearXiv

A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs

  • Zhiqiang Xu
Open at sourcePDFDOICite

Abstract

We give a deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs. For every finite simple bipartite graph of maximum degree at most an integer Δ≥3, the algorithm assigns signs to its edges so that the signed adjacency matrix has operator norm strictly less than 2√(Δ−1). Our algorithm builds on the randomized recursive repair framework of Jadbabaie, Saberi, and Sra~\cite{JSS26}, with deterministic rules for sign selection and vertex deletion.

Related

  1. A Polynomial-Time Algorithm for the Minimal Input/Output Node Cardinality Disturbance Decoupling Problem via Output Feedback
    Luca Claude Gino Lebon, Jorke de Vlas, Johannes K. Fichte +1
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  2. A tight 1/3-approximation algorithm and fully polynomial-time approximation schemes for the Colored Knapsack Problem
    Fabio Ciccarelli, Fabio Furini
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  3. Three-phase time minimization transportation problem with non-idle phases: a polynomial two-witness algorithm
    Sailesh Kamalahasan, Raghav Paladugu, Archana Khurana
    arXivPreprintCC BY-NC-ND 4.0Full textOptimisation & controlarXiv
  4. Deterministic and Random Bipartite Matching on General Networks: Convex Flow Reformulation, Asymptotic Properties, and Fast Algorithms
    Yuhui Zhai, Yanfeng Ouyang
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv
  5. The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach
    Yiyu Qiu, Wei Chen, H. Vincent Poor
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{xu2026deterministic,
  title = {{A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs}},
  author = {Zhiqiang Xu},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.09972},
  eprint = {2610.09972},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.09972},
}
RIS
TY  - UNPB
TI  - A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs
AU  - Zhiqiang Xu
PY  - 2026
DA  - 2026/10/26
PB  - arXiv
DO  - 10.48550/arxiv.2610.09972
UR  - https://arxiv.org/abs/2610.09972
AB  - We give a deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs. For every finite simple bipartite graph of maximum degree at most an integer Δ≥3, the algorithm assigns signs to its edges so that the signed adjacency matrix has operator norm strictly less than 2√(Δ−1). Our algorithm builds on the randomized recursive repair framework of Jadbabaie, Saberi, and Sra~\cite{JSS26}, with deterministic rules for sign selection and vertex deletion.
ER  -