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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Poljak and Turz\'ik (Discrete Math. 1986) introduced the notion of\lambda-extendible properties of graphs as a generalization of the property ofbeing bipartite. They showed that for any 0<\lambda<1 and \lambda-extendibleproperty \Pi, any connected graph G on n vertices and m edges contains asubgraph H \in {\Pi} with at least \lambda m+ (1-\lambda)/2 (n-1) edges. Theproperty of being bipartite is 1/2-extendible, and thus this bound generalizesthe Edwards-Erd\H{o}s bound for Max-Cut.  We define a variant, namely strong \lambda-extendibility, to which the boundapplies. For a strongly \lambda-extendible graph property \Pi, we define theparameterized Above Poljak- Turz\'ik (APT) (\Pi) problem as follows: Given aconnected graph G on n vertices and m edges and an integer parameter k, doesthere exist a spanning subgraph H of G such that H \in {\Pi} and H has at least\lambda m + (1-\lambda)/2 (n - 1) + k edges? The parameter is k, the surplusover the number of edges guaranteed by the Poljak-Turz\'ik bound.  We consider properties {\Pi} for which APT (\Pi) is fixed- parametertractable (FPT) on graphs which are O(k) vertices away from being a graph inwhich each block is a clique. We show that for all such properties, APT (\Pi)is FPT for all 0<\lambda<1. Our results hold for properties of oriented graphsand graphs with edge labels. Our results generalize the result of Crowston etal. (ICALP 2012) on Max-Cut parameterized above the Edwards-Erd\H{o}s bound,and yield FPT algorithms for several graph problems parameterized above lowerbounds, e.g., Max q-Colorable Subgraph problem. Our results also imply that theparameterized above-guarantee Oriented Max Acyclic Digraph problem is FPT, thussolving an open question of Raman and Saurabh (Theor. Comput. Sci. 2006).

Beyond Max-Cut: \lambda-Extendible Properties Parameterized Above the Poljak-Turz\'{i}k Bound