How to get a degree-anonymous graph using minimum number of edge rotations

Cristina Bazgan; Pierre Cazals; Janka Chlebikova

doi:10.1007/978-3-030-64843-5_17

How to get a degree-anonymous graph using minimum number of edge rotations

Cristina Bazgan, Pierre Cazals, Janka Chlebikova

School of Computing

Universite Paris Dauphine

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

58 Downloads (Pure)

Abstract

A graph is k-degree-anonymous if for each vertex there are at least (k-1) other vertices of the same degree in the graph. The Min Anonymous-Edge-Rotation problem asks for a given graph G and a positive integer k to find a minimum number of edge rotations that transform G into a k-degree-anonymous graph. In this paper, we establish sufficient conditions for an input graph and k ensuring that a solution for the problem exists. We also prove that the Min Anonymous-Edge-Rotation problem is NP-hard even for k=n/3, where n is the order of a graph. On the positive side, we argue that under some constraints on the number of edges in a graph and k, Min Anonymous-Edge-Rotation is polynomial-time 2-approximable. Moreover, we show that the problem is solvable in polynomial time for any graph when k=n and for trees when k=θ(n).

Original language	English
Title of host publication	Combinatorial Optimization and Applications
Subtitle of host publication	14th International Conference, COCOA 2020, Dallas, TX, USA, December 11–13, 2020, Proceedings
Editors	Weili Wu, Zhongnan Zhang
Publisher	Springer
Pages	242-256
Number of pages	12
ISBN (Electronic)	978-3-030-64843-5
ISBN (Print)	978-3-030-64842-8
DOIs	https://doi.org/10.1007/978-3-030-64843-5_17
Publication status	Published - 4 Dec 2020
Event	14th Annual International Conference on Combinatorial Optimization and Applications - Dallas, United States Duration: 11 Dec 2020 → 13 Dec 2020 Conference number: 14 https://theory.utdallas.edu/COCOA2020/index.html

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	12577
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th Annual International Conference on Combinatorial Optimization and Applications
Abbreviated title	COCOA
Country/Territory	United States
City	Dallas
Period	11/12/20 → 13/12/20
Internet address	https://theory.utdallas.edu/COCOA2020/index.html

Keywords

degree-anonymous graph
edge rotations
NPhardness
approximation algorithm

Access to Document

10.1007/978-3-030-64843-5_17

Cocoa2020
This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at: http://dx.doi.org/10.1007/978-3-030-64843-5_17.
Accepted author manuscript (Post-print), 356 KB

https://theory.utdallas.edu/COCOA2020/

Cite this

Bazgan, C., Cazals, P., & Chlebikova, J. (2020). How to get a degree-anonymous graph using minimum number of edge rotations. In W. Wu, & Z. Zhang (Eds.), Combinatorial Optimization and Applications: 14th International Conference, COCOA 2020, Dallas, TX, USA, December 11–13, 2020, Proceedings (pp. 242-256). (Lecture Notes in Computer Science; Vol. 12577). Springer. https://doi.org/10.1007/978-3-030-64843-5_17

Bazgan, Cristina ; Cazals, Pierre ; Chlebikova, Janka. / How to get a degree-anonymous graph using minimum number of edge rotations. Combinatorial Optimization and Applications: 14th International Conference, COCOA 2020, Dallas, TX, USA, December 11–13, 2020, Proceedings. editor / Weili Wu ; Zhongnan Zhang. Springer, 2020. pp. 242-256 (Lecture Notes in Computer Science).

@inproceedings{fd40d45a62f040428f9574b7f93fabff,

title = "How to get a degree-anonymous graph using minimum number of edge rotations",

abstract = "A graph is k-degree-anonymous if for each vertex there are at least (k-1) other vertices of the same degree in the graph. The Min Anonymous-Edge-Rotation problem asks for a given graph G and a positive integer k to find a minimum number of edge rotations that transform G into a k-degree-anonymous graph. In this paper, we establish sufficient conditions for an input graph and k ensuring that a solution for the problem exists. We also prove that the Min Anonymous-Edge-Rotation problem is NP-hard even for k=n/3, where n is the order of a graph. On the positive side, we argue that under some constraints on the number of edges in a graph and k, Min Anonymous-Edge-Rotation is polynomial-time 2-approximable. Moreover, we show that the problem is solvable in polynomial time for any graph when k=n and for trees when k=θ(n).",

keywords = "degree-anonymous graph, edge rotations, NPhardness, approximation algorithm",

author = "Cristina Bazgan and Pierre Cazals and Janka Chlebikova",

note = "12 month embargo. Reference to Appendix in AAM not there in VoR, Fig. 1 present; 14th Annual International Conference on Combinatorial Optimization and Applications, COCOA ; Conference date: 11-12-2020 Through 13-12-2020",

year = "2020",

month = dec,

day = "4",

doi = "10.1007/978-3-030-64843-5_17",

language = "English",

isbn = "978-3-030-64842-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "242--256",

editor = "Weili Wu and Zhongnan Zhang",

booktitle = "Combinatorial Optimization and Applications",

url = "https://theory.utdallas.edu/COCOA2020/index.html",

}

Bazgan, C, Cazals, P & Chlebikova, J 2020, How to get a degree-anonymous graph using minimum number of edge rotations. in W Wu & Z Zhang (eds), Combinatorial Optimization and Applications: 14th International Conference, COCOA 2020, Dallas, TX, USA, December 11–13, 2020, Proceedings. Lecture Notes in Computer Science, vol. 12577, Springer, pp. 242-256, 14th Annual International Conference on Combinatorial Optimization and Applications, Dallas, Texas, United States, 11/12/20. https://doi.org/10.1007/978-3-030-64843-5_17

How to get a degree-anonymous graph using minimum number of edge rotations. / Bazgan, Cristina; Cazals, Pierre; Chlebikova, Janka.
Combinatorial Optimization and Applications: 14th International Conference, COCOA 2020, Dallas, TX, USA, December 11–13, 2020, Proceedings. ed. / Weili Wu; Zhongnan Zhang. Springer, 2020. p. 242-256 (Lecture Notes in Computer Science; Vol. 12577).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - How to get a degree-anonymous graph using minimum number of edge rotations

AU - Bazgan, Cristina

AU - Cazals, Pierre

AU - Chlebikova, Janka

N1 - Conference code: 14

PY - 2020/12/4

Y1 - 2020/12/4

N2 - A graph is k-degree-anonymous if for each vertex there are at least (k-1) other vertices of the same degree in the graph. The Min Anonymous-Edge-Rotation problem asks for a given graph G and a positive integer k to find a minimum number of edge rotations that transform G into a k-degree-anonymous graph. In this paper, we establish sufficient conditions for an input graph and k ensuring that a solution for the problem exists. We also prove that the Min Anonymous-Edge-Rotation problem is NP-hard even for k=n/3, where n is the order of a graph. On the positive side, we argue that under some constraints on the number of edges in a graph and k, Min Anonymous-Edge-Rotation is polynomial-time 2-approximable. Moreover, we show that the problem is solvable in polynomial time for any graph when k=n and for trees when k=θ(n).

AB - A graph is k-degree-anonymous if for each vertex there are at least (k-1) other vertices of the same degree in the graph. The Min Anonymous-Edge-Rotation problem asks for a given graph G and a positive integer k to find a minimum number of edge rotations that transform G into a k-degree-anonymous graph. In this paper, we establish sufficient conditions for an input graph and k ensuring that a solution for the problem exists. We also prove that the Min Anonymous-Edge-Rotation problem is NP-hard even for k=n/3, where n is the order of a graph. On the positive side, we argue that under some constraints on the number of edges in a graph and k, Min Anonymous-Edge-Rotation is polynomial-time 2-approximable. Moreover, we show that the problem is solvable in polynomial time for any graph when k=n and for trees when k=θ(n).

KW - degree-anonymous graph

KW - edge rotations

KW - NPhardness

KW - approximation algorithm

U2 - 10.1007/978-3-030-64843-5_17

DO - 10.1007/978-3-030-64843-5_17

M3 - Conference contribution

SN - 978-3-030-64842-8

T3 - Lecture Notes in Computer Science

SP - 242

EP - 256

BT - Combinatorial Optimization and Applications

A2 - Wu, Weili

A2 - Zhang, Zhongnan

PB - Springer

T2 - 14th Annual International Conference on Combinatorial Optimization and Applications

Y2 - 11 December 2020 through 13 December 2020

ER -

Bazgan C, Cazals P, Chlebikova J. How to get a degree-anonymous graph using minimum number of edge rotations. In Wu W, Zhang Z, editors, Combinatorial Optimization and Applications: 14th International Conference, COCOA 2020, Dallas, TX, USA, December 11–13, 2020, Proceedings. Springer. 2020. p. 242-256. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-64843-5_17

How to get a degree-anonymous graph using minimum number of edge rotations

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this