Large cuts with local algorithms on triangle-free graphs (Q2411507)

From MaRDI portal
Revision as of 20:33, 2 February 2024 by Import240129110113 (talk | contribs) (Added link to MaRDI item.)
scientific article
Language Label Description Also known as
English
Large cuts with local algorithms on triangle-free graphs
scientific article

    Statements

    Large cuts with local algorithms on triangle-free graphs (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    24 October 2017
    0 references
    Summary: Let \(G\) be a \(d\)-regular triangle-free graph with \(m\) edges. We present an algorithm which finds a cut in \(G\) with at least \((1/2 + 0.28125/\sqrt{d})m\) edges in expectation, improving upon Shearer's classic result. In particular, this implies that any \(d\)-regular triangle-free graph has a cut of at least this size, and thus, we obtain a new lower bound for the maximum number of edges in a bipartite subgraph of \(G\). Our algorithm is simpler than Shearer's classic algorithm and it can be interpreted as a very efficient \textit{randomised distributed (local) algorithm}: each node needs to produce only one random bit, and the algorithm runs in one round. The randomised algorithm itself was discovered using \textit{computational techniques}. We show that for any fixed \(d\), there exists a weighted neighbourhood graph \(\mathcal{N}_d\) such that there is a one-to-one correspondence between heavy cuts of \(\mathcal{N}_d\) and randomised local algorithms that find large cuts in any \(d\)-regular input graph. This turns out to be a useful tool for analysing the existence of cuts in \(d\)-regular graphs: we can compute the optimal cut of \(\mathcal{N}_d\) to attain a lower bound on the maximum cut size of any \(d\)-regular triangle-free graph.
    0 references
    graph theory
    0 references
    regular graphs
    0 references
    cuts
    0 references

    Identifiers