Beyond Max-Cut: \(\lambda\)-extendible properties parameterized above the Poljak-Turzík bound

DOI10.1016/j.jcss.2014.04.011zbMath1312.68105arXiv1207.5696MaRDI QIDQ2453557

Geevarghese Philip, Matthias Mnich, Saket Saurabh, Ondřej Suchý

Publication date: 10 June 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1207.5696

zbMATH Keywords

algorithms and data structures; fixed-parameter tractable algorithms; \textsc{Max-Cut}; \(\lambda\)-extendible properties; above-guarantee parameterization

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

05C40: Connectivity

Related Items

Parameterized Traveling Salesman Problem: Beating the Average, Linear kernels and linear-time algorithms for finding large cuts, An improved kernel for max-bisection above tight lower bound, Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}, Acyclic Digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized complexity of MaxSat above average
• A probabilistic approach to problems parameterized above or below tight bounds
• Solving MAX-\(r\)-SAT above a tight lower bound
• Parameterized algorithms for feedback set problems and their duals in tournaments
• Parameterizing above or below guaranteed values
• A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• On some extremal problems in graph theory
• Parametrized complexity theory.
• Max-Cut Parameterized above the Edwards-Erdős Bound
• Simultaneously Satisfying Linear Equations Over F_2: MaxLin2 and Max-r-Lin2 Parameterized Above Average
• Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound
• Polynomial Kernels for {\lambda}-extendible Properties Parameterized Above the Poljak-Turz\'ik Bound
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Reducibility among Combinatorial Problems
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Optimal ranking of tournaments
• Some Extremal Properties of Bipartite Subgraphs