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 条

[31] Minimum Manhattan Network is NP-Complete [J].

Chin, Francis Y. L. ;

Guo, Zeyu ;

Sun, He .

PROCEEDINGS OF THE TWENTY-FIFTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SCG'09), 2009, :393-402

[32] On unapproximable versions of NP-complete problems [J].

Zuckerman, D .

SIAM JOURNAL ON COMPUTING, 1996, 25 (06) :1293-1304

[33] Zen Puzzle Garden is NP-complete [J].

Houston, Robin ;

White, Joseph ;

Amos, Martyn .

INFORMATION PROCESSING LETTERS, 2012, 112 (03) :106-108

[34] Searching for capacity factors is NP-complete [J].

Li, Yuan ;

Huang, Zheng ;

Wang, Xin ;

Kan, Haibin .

2008 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS, PROCEEDINGS, VOLS 1-13, 2008, :1431-1435

[35] Computing quantum discord is NP-complete [J].

Huang, Yichen .

NEW JOURNAL OF PHYSICS, 2014, 16

[36] Moon-or-Sun, Nagareru, and Nurimeizu are NP-Complete [J].

Iwamoto, Chuzo ;

Ide, Tatsuya .

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2022, E105A (09) :1187-1194

[37] The Cophylogeny Reconstruction Problem Is NP-Complete [J].

Ovadia, Y. ;

Fielder, D. ;

Conow, C. ;

Libeskind-Hadas, R. .

JOURNAL OF COMPUTATIONAL BIOLOGY, 2011, 18 (01) :59-65

[38] An NP-complete fragment of fibring logic [J].

Yin Wu ;

Min Jiang ;

Zhongqiang Huang ;

Fei Chao ;

Changle Zhou .

Annals of Mathematics and Artificial Intelligence, 2015, 75 :391-417

[39] The Bandwidth Allocation Problem in the ATM network model is NP-complete [J].

Vedantham, S ;

Iyengar, SS .

INFORMATION PROCESSING LETTERS, 1998, 65 (04) :179-182

[40] Timed protocol insecurity problem is NP-complete [J].

Benerecetti, Massimo ;

Peron, Adriano .

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE, 2013, 29 (03) :843-862

← 1 2 3 4 5 →