English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

A graph $G$ is signed if each edge is assigned $+$ or $-$. A signed graph isbalanced if there is a bipartition of its vertex set such that an edge has sign$-$ if and only if its endpoints are in different parts. The Edwards-Erd\"osbound states that every graph with $n$ vertices and $m$ edges has a balancedsubgraph with at least $\frac{m}{2}+\frac{n-1}{4}$ edges. In the Signed Max CutAbove Tight Lower Bound (Signed Max Cut ATLB) problem, given a signed graph $G$and a parameter $k$, the question is whether $G$ has a balanced subgraph withat least $\frac{m}{2}+\frac{n-1}{4}+\frac{k}{4}$ edges. This problemgeneralizes Max Cut Above Tight Lower Bound, for which a kernel with $O(k^5)$vertices was given by Crowston et al. [ICALP 2012, Algorithmica 2015]. Crowstonet al. [TCS 2013] improved this result by providing a kernel with $O(k^3)$vertices for the more general Signed Max Cut ATLB problem. In this article weare interested in improving the size of the kernels for Signed Max Cut ATLB onrestricted graph classes for which the problem remains hard. For two integers$r,\ell \geq 0$, a graph $G$ is an $(r,\ell)$-graph if $V(G)$ can bepartitioned into $r$ independent sets and $\ell$ cliques. Building on thetechniques of Crowston et al. [TCS 2013], we provide a kernel with $O(k^2)$vertices on $(r,\ell)$-graphs for any fixed $r,\ell \geq 0$, and a simplelinear kernel on subclasses of split graphs for which we prove that the problemis still NP-hard.

Improved kernels for Signed Max Cut parameterized above lower bound on (r,l)-graphs