License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.69
URN: urn:nbn:de:0030-drops-81374
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8137/
Go to the corresponding LIPIcs Volume Portal

Vikas, Narayan

Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon

pdf-format:
LIPIcs-MFCS-2017-69.pdf (0.4 MB)

Abstract

In this paper, we solve a long-standing graph partition problem under vertex-compaction that has been of interest since about 1999. The graph partition problem that we consider in this paper is to decide whether or not it is possible to partition the vertices of a graph into six distinct non-empty sets A, B, C, D, E, and F, such that the vertices in each set are independent, i.e., there is no edge within any set, and an edge is possible but not necessary only between the pairs of sets A and B, B and C, C and D, D and E, E and F, and F and A, and there is no edge between any other pair of sets. We study the problem as the vertex-compaction problem for an irreflexive hexagon (6-cycle). Determining the computational complexity of this problem has been a long-standing problem of interest since about 1999, especially after the results of open problems obtained by the author on a related compaction problem appeared in 1999. We show in this paper that the vertex-compaction problem for an irreflexive hexagon is NP-complete. Our proof can be extended for larger even irreflexive cycles, showing that the vertex-compaction problem for an irreflexive even k-cycle is NP-complete, for all even k \geq 6.

BibTeX - Entry

@InProceedings{vikas:LIPIcs:2017:8137,
  author =	{Narayan Vikas},
  title =	{{Computational Complexity of Graph Partition under Vertex-Compaction to an Irreflexive Hexagon}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{69:1--69:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8137},
  URN =		{urn:nbn:de:0030-drops-81374},
  doi =		{10.4230/LIPIcs.MFCS.2017.69},
  annote =	{Keywords: computational complexity, algorithms, graph, partition, colouring, homomorphism, retraction, compaction, vertex-compaction}
}

Keywords: computational complexity, algorithms, graph, partition, colouring, homomorphism, retraction, compaction, vertex-compaction
Collection: 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Issue Date: 2017
Date of publication: 01.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI