Sparse balanced partitions and the complexity of subgraph problems

Noga Alon; Dániel Marx

doi:10.1137/100812653

Sparse balanced partitions and the complexity of subgraph problems

Noga Alon, Dániel Marx

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

Abstract

We consider the problem of partitioning the vertices of an n-vertex graph with maximum degree d into k classes V₁;⋯, V_k of size at most ⌊n/k⌋ in a way that minimizes the number of pairs (i,j) for which there is an edge between V_i and V_j. We show that there is always such a partition with O(k^2-2/d) adjacent pairs, and this bound is tight. This problem is related to questions about the depth of certain graph embeddings, which have been used in the study of the complexity of subgraph and constraint satisfaction problems.

Original language	English (US)
Pages (from-to)	631-644
Number of pages	14
Journal	SIAM Journal on Discrete Mathematics
Volume	25
Issue number	2
DOIs	https://doi.org/10.1137/100812653
State	Published - 2011
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Mathematics

Keywords

Graph partitions
Minors
Subgraph problems

Access to Document

10.1137/100812653

Cite this

@article{d65d873176cc464d93d4f6357bb8a124,

title = "Sparse balanced partitions and the complexity of subgraph problems",

abstract = "We consider the problem of partitioning the vertices of an n-vertex graph with maximum degree d into k classes V1;⋯, Vk of size at most ⌊n/k⌋ in a way that minimizes the number of pairs (i,j) for which there is an edge between Vi and Vj. We show that there is always such a partition with O(k2-2/d) adjacent pairs, and this bound is tight. This problem is related to questions about the depth of certain graph embeddings, which have been used in the study of the complexity of subgraph and constraint satisfaction problems.",

keywords = "Graph partitions, Minors, Subgraph problems",

author = "Noga Alon and D{\'a}niel Marx",

year = "2011",

doi = "10.1137/100812653",

language = "English (US)",

volume = "25",

pages = "631--644",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}

TY - JOUR

T1 - Sparse balanced partitions and the complexity of subgraph problems

AU - Alon, Noga

AU - Marx, Dániel

PY - 2011

Y1 - 2011

N2 - We consider the problem of partitioning the vertices of an n-vertex graph with maximum degree d into k classes V1;⋯, Vk of size at most ⌊n/k⌋ in a way that minimizes the number of pairs (i,j) for which there is an edge between Vi and Vj. We show that there is always such a partition with O(k2-2/d) adjacent pairs, and this bound is tight. This problem is related to questions about the depth of certain graph embeddings, which have been used in the study of the complexity of subgraph and constraint satisfaction problems.

AB - We consider the problem of partitioning the vertices of an n-vertex graph with maximum degree d into k classes V1;⋯, Vk of size at most ⌊n/k⌋ in a way that minimizes the number of pairs (i,j) for which there is an edge between Vi and Vj. We show that there is always such a partition with O(k2-2/d) adjacent pairs, and this bound is tight. This problem is related to questions about the depth of certain graph embeddings, which have been used in the study of the complexity of subgraph and constraint satisfaction problems.

KW - Graph partitions

KW - Minors

KW - Subgraph problems

UR - http://www.scopus.com/inward/record.url?scp=79960587880&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79960587880&partnerID=8YFLogxK

U2 - 10.1137/100812653

DO - 10.1137/100812653

M3 - Article

AN - SCOPUS:79960587880

SN - 0895-4801

VL - 25

SP - 631

EP - 644

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -

Sparse balanced partitions and the complexity of subgraph problems

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this