The decision problem MaxC ut 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 M axC ut 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.
MaxC ut on permutation graphs is NP-complete / de Figueiredo C.M.H.; de Melo A.A.; Oliveira F.S.; Silva Ana Shirley. - In: JOURNAL OF GRAPH THEORY. - ISSN 0364-9024. - STAMPA. - 104:(2023), pp. 5-16. [10.1002/jgt.22948]
MaxC ut on permutation graphs is NP-complete
Silva Ana Shirley
2023
Abstract
The decision problem MaxC ut 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 M axC ut 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.
| File | Dimensione | Formato | |
|---|---|---|---|
|
MaxCut on permutation graphs is NP‐complete JGT.pdf
Accesso chiuso
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
752.46 kB
Formato
Adobe PDF
|
752.46 kB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
