Equipartitions of graphs

David Eppstein, Joan Feigenbaum, Chung Lun Li

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

Let G be an undirected graph on n nodes, and let k be an integer that divides n. A k-equipartition π of G is a partition of V(G) into k equal-sized pieces V1,⋯,Vk. A pair Vi, Vjof distinct sets in π is called a bad pair if there is at least one edge vivjof E(G) such that viε{lunate}Viand vjε{lunate} Vj. The parameterized equipartition problem is: given G and k, find an optimal k-equipartition of G, i.e., one with the smallest possible number of bad pairs. More generally, a nontrivial equipartition of G is a k-equipartition, for some proper divisor k of n. The equipartition problem is: given G, find a nontrivial equipartition with the minimum number of bad pairs, where the minimum is taken over all divisors k of n and all k-equipartitions. We prove that there are relatively sparse graphs all of whose equipartitions have the maximum number of bad pairs (up to constant factors). We also prove that the parameterized and unparameterized versions of the equipartition problem are NP-hard.
Original languageEnglish
Pages (from-to)239-248
Number of pages10
JournalDiscrete Mathematics
Volume91
Issue number3
DOIs
Publication statusPublished - 12 Sep 1990
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Cite this