MaxCut on permutation graphs is NP-complete

被引：0
|
作者：
de Figueiredo, Celina M. H. [1 ]
de Melo, Alexsander A. [1 ]
Oliveira, Fabiano S. [2 ]
Silva, Ana [3 ]
机构：
[1] Fed Univ Rio Janeiro, COPPE, Rio De Janeiro, Brazil
[2] Rio Janeiro State Univ, IME, Rio De Janeiro, Brazil
[3] Univ Fed Ceara, Dept Math, Fortaleza, CE, Brazil
来源：
JOURNAL OF GRAPH THEORY | 2023年 / 104卷 / 01期
关键词：
computational complexity; maximum cut; NP-complete; permutation graphs;
D O I：
10.1002/jgt.22948
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
The decision problem MaxCut is known to be NP-complete since the seventies, but only recently its restriction to interval graphs has been announced to be hard by Adhikary, Bose, Mukherjee, and Roy. Building on their proof, in this paper we prove that the MaxCut problem is NP-complete on permutation graphs. This settles a long-standing open problem that appeared in the 1985 column of the Ongoing Guide to NP-completeness by David S. Johnson, and is the first NP-hardness entry for permutation graphs in such column.
引用
收藏
页码：5 / 16
页数：12
相关论文
共 50 条
  • [1] The harmonious coloring problem is NP-complete for interval and permutation graphs
    Asdre, Katerina
    Ioannidou, Kyriaki
    Nikolopoulos, Stavros D.
    DISCRETE APPLIED MATHEMATICS, 2007, 155 (17) : 2377 - 2382
  • [2] THE EDGE HAMILTONIAN PATH PROBLEM IS NP-COMPLETE FOR BIPARTITE GRAPHS
    LAI, TH
    WEI, SS
    INFORMATION PROCESSING LETTERS, 1993, 46 (01) : 21 - 26
  • [3] APPROXIMATION ALGORITHMS FOR NP-COMPLETE PROBLEMS ON PLANAR GRAPHS
    BAKER, BS
    JOURNAL OF THE ACM, 1994, 41 (01) : 153 - 180
  • [4] Maximum Cut on Interval Graphs of Interval Count Four is NP-Complete
    de Figueiredo, Celina M. H.
    de Melo, Alexsander A.
    Oliveira, Fabiano S.
    Silva, Ana
    DISCRETE & COMPUTATIONAL GEOMETRY, 2024, 71 (03) : 893 - 917
  • [5] Maximum Cut on Interval Graphs of Interval Count Four is NP-Complete
    Celina M. H. de Figueiredo
    Alexsander A. de Melo
    Fabiano S. Oliveira
    Ana Silva
    Discrete & Computational Geometry, 2024, 71 : 893 - 917
  • [6] Generalized Pyramid is NP-Complete
    Iwamoto, Chuzo
    Matsui, Yuta
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2013, E96D (11) : 2462 - 2465
  • [7] 2-subcoloring is NP-complete for planar comparability graphs
    Ochem, Pascal
    INFORMATION PROCESSING LETTERS, 2017, 128 : 46 - 48
  • [8] The weighted independent domination problem is NP-complete for chordal graphs
    Chang, GJ
    DISCRETE APPLIED MATHEMATICS, 2004, 143 (1-3) : 351 - 352
  • [9] Hashiwokakero is NP-complete
    Andersson, Daniel
    INFORMATION PROCESSING LETTERS, 2009, 109 (19) : 1145 - 1146
  • [10] Rikudo is NP-complete
    Viet-Ha Nguyen
    Perrot, Kevin
    THEORETICAL COMPUTER SCIENCE, 2022, 910 : 34 - 47
12345