Beyond Max-Cut: -extendible properties parameterized above the Poljak-Turzík bound
From MaRDI portal
Publication:2453557
Abstract: Poljak and Turz'ik (Discrete Math. 1986) introduced the notion of lambda-extendible properties of graphs as a generalization of the property of being bipartite. They showed that for any 0<lambda<1 and lambda-extendible property Pi, any connected graph G on n vertices and m edges contains a subgraph H in {Pi} with at least lambda m+ (1-lambda)/2 (n-1) edges. The property of being bipartite is 1/2-extendible, and thus this bound generalizes the Edwards-ErdH{o}s bound for Max-Cut. We define a variant, namely strong lambda-extendibility, to which the bound applies. For a strongly lambda-extendible graph property Pi, we define the parameterized Above Poljak- Turz'ik (APT) (Pi) problem as follows: Given a connected graph G on n vertices and m edges and an integer parameter k, does there 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 surplus over the number of edges guaranteed by the Poljak-Turz'ik bound. We consider properties {Pi} for which APT (Pi) is fixed- parameter tractable (FPT) on graphs which are O(k) vertices away from being a graph in which 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 graphs and graphs with edge labels. Our results generalize the result of Crowston et al. (ICALP 2012) on Max-Cut parameterized above the Edwards-ErdH{o}s bound, and yield FPT algorithms for several graph problems parameterized above lower bounds, e.g., Max q-Colorable Subgraph problem. Our results also imply that the parameterized above-guarantee Oriented Max Acyclic Digraph problem is FPT, thus solving an open question of Raman and Saurabh (Theor. Comput. Sci. 2006).
Recommendations
- Beyond Max-Cut: -extendible properties parameterized above the Poljak-Turzík bound
- Polynomial kernels for -extendible properties parameterized above the Poljak-Turzík bound
- Max-Cut parameterized above the Edwards-Erdős bound
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Linear kernels and linear-time algorithms for finding large cuts
Cites work
- A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
- A probabilistic approach to problems parameterized above or below tight bounds
- Beyond Max-Cut: -extendible properties parameterized above the Poljak-Turzík bound
- Directed acyclic subgraph problem parameterized above the Poljak-Turzík bound
- Graph theory
- scientific article; zbMATH DE number 3510345 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 1787231 (Why is no real title available?)
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
- Max-Cut parameterized above the Edwards-Erdős bound
- On some extremal problems in graph theory
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Optimal ranking of tournaments
- Parameterized algorithms for feedback set problems and their duals in tournaments
- Parameterizing above Guaranteed Values: MaxSat and MaxCut
- Parameterizing above or below guaranteed values
- Parametrized complexity theory.
- Polynomial kernels for -extendible properties parameterized above the Poljak-Turzík bound
- Reducibility among combinatorial problems
- Simultaneously satisfying linear equations over \(\mathbb {F}_2\): MaxLin2 and Max-\(r\)-Lin2 parameterized above average
- Solving MAX-\(r\)-SAT above a tight lower bound
- Some Extremal Properties of Bipartite Subgraphs
Cited in
(9)- An improved kernel for max-bisection above tight lower bound
- Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}
- Beyond Max-Cut: -extendible properties parameterized above the Poljak-Turzík bound
- Polynomial kernels for -extendible properties parameterized above the Poljak-Turzík bound
- Acyclic digraphs
- Parameterized traveling salesman problem: beating the average
- Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound
- Linear kernels and linear-time algorithms for finding large cuts
- Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound
This page was built for publication: Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2453557)
