Note on maximal bisection above tight lower bound

DOI10.1016/J.IPL.2010.08.001MaRDI QIDQ1675768zbMATH OpenOpenAlexFDO

Authors G. Gutin, A. Yeo

Publication date 3 November 2017

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

algorithmsfixed-parameter tractabilitykernels

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In a graph $G=(V,E)$, a bisection $(X,Y)$ is a partition of $V$ into sets $X$ and $Y$ such that $|X|le|Y|le|X|+1$. The size of $(X,Y)$ is the number of edges between $X$ and $Y$. In the Max Bisection problem we are given a graph $G=(V,E)$ and are required to find a bisection of maximum size. It is not hard to see that $lceil|E|/2ceil$ is a tight lower bound on the maximum size of a bisection of $G$. We study parameterized complexity of the following parameterized problem called Max Bisection above Tight Lower Bound (Max-Bisec-ATLB): decide whether a graph $G=(V,E)$ has a bisection of size at least $lceil|E|/2ceil+k,$ where $k$ is the parameter. We show that this parameterized problem has a kernel with $O(k^2)$ vertices and $O(k^3)$ edges, i.e., every instance of Max-Bisec-ATLB is equivalent to an instance of Max-Bisec-ATLB on a graph with at most $O(k^2)$ vertices and $O(k^3)$ edges.

Recommendations

• Bisections above Tight Lower Bounds
• A new kernel for parameterized Max-Bisection above tight lower bound
• An improved kernel for max-bisection above tight lower bound
• Bisections of graphs
• On the parameterized complexity of computing graph bisections

Cites work

• scientific article; zbMATH DE number 1324671 (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?)
• scientific article; zbMATH DE number 6297727 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A probabilistic approach to problems parameterized above or below tight bounds
• Approximation and intractability results for the maximum cut problem and its variants
• Betweenness parameterized above tight lower bound
• Fixed-parameter complexity of minimum profile problems
• Interval Completion Is Fixed Parameter Tractable
• Kernel Bounds for Disjoint Cycles and Disjoint Paths
• Note on Max Lin-2 above average
• On problems without polynomial kernels
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Parameterizing above or below guaranteed values
• Parametrized complexity theory.
• Some Extremal Properties of Bipartite Subgraphs
• Systems of linear equations over \(\mathbb{F}_2\) and problems parameterized above average
• The complexity of König subgraph problems and above-guarantee vertex cover
• The linear arrangement problem parameterized above guaranteed value
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Vertex cover problem parameterized above and below tight bounds
• \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves

Cited in

(11)

• Maximum balanced subgraph problem parameterized above lower bound
• Balanced judicious bipartition is fixed-parameter tractable
• On the parameterized complexity of computing graph bisections
• A new kernel for parameterized Max-Bisection above tight lower bound
• Balanced Judicious Bipartition is Fixed-Parameter Tractable
• An improved kernel for max-bisection above tight lower bound
• Linear kernels and linear-time algorithms for finding large cuts
• Satisfying more than half of a system of linear equations over GF(2): a multivariate approach
• Bisections above Tight Lower Bounds
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• Parameterized constraint satisfaction problems: a survey

This page was built for publication: Note on maximal bisection above tight lower bound

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1675768)