2020/06/06 by Arman Boyacı, Tınaz Ekim, Boyacı, Arman +3
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2006.03856
openalex publication_date 2020/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Although it has been claimed in two different papers that the maximum\ncardinality cut problem is polynomial-time solvable for proper interval graphs,\nboth of them turned out to be erroneous. In this paper, we give FPT algorithms\nfor the maximum cardinality cut problem in classes of graphs containing proper\ninterval graphs and mixed unit interval graphs when parameterized by some new\nparameters that we introduce. These new parameters are related to a\ngeneralization of the so-called bubble representations of proper interval\ngraphs and mixed unit interval graphs and to clique-width decompositions.\n