Complexity of maximum cut on interval graphs

DOI10.1007/s00454-022-00472-yarXiv2006.00061OpenAlexW3029513181MaRDI QIDQ6174803

Satwik Mukherjee, Kaustav Bose, Ranendu Adhikary, Bodhayan Roy

Publication date: 17 August 2023

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

maximum cutNP-completeinterval graph

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

MaxCut on permutation graphs is NP‐complete ⋮ Maximum cut on interval graphs of interval count four is NP-complete ⋮ Complexity of maximum cut on interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for the weighted feedback vertex problem on interval graphs
• \textsc{max-cut} and containment relations in graphs
• \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
• A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
• The max-cut problem on graphs not contractible to \(K_ 5\)
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
• Finding Hamiltonian circuits in interval graphs
• Optimization, approximation, and complexity classes
• Generalized vertex covering in interval graphs
• Maximum cut on line and total graphs
• Achromatic number is NP-complete for cographs and interval graphs
• Algorithmic graph theory and perfect graphs
• Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}
• An improved fixed-parameter algorithm for max-cut parameterized by crossing number
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
• The harmonious coloring problem is NP-complete for interval and permutation graphs
• A short proof of the NP-completeness of minimum sum interval coloring
• A new representation of proper interval graphs with an application to clique-width
• Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
• On the power of unique 2-prover 1-round games
• The NP-completeness column: an ongoing guide
• An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Gadgets, Approximation, and Linear Programming
• Reducibility among Combinatorial Problems
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• Some optimal inapproximability results
• Optimal Linear Arrangement of Interval Graphs
• Complexity of maximum cut on interval graphs

This page was built for publication: Complexity of maximum cut on interval graphs