research-article

Win-win kernelization for degree sequence completion problems

Authors:

Vincent Froese,

André Nichterlein,

Rolf NiedermeierAuthors Info & Claims

Journal of Computer and System Sciences, Volume 82, Issue 6

Pages 1100 - 1111

https://doi.org/10.1016/j.jcss.2016.03.009

Published: 01 September 2016 Publication History

Abstract

We study provably effective and efficient data reduction for a class of NP-hard graph modification problems based on vertex degree properties. We show fixed-parameter tractability for NP-hard graph completion (that is, edge addition) cases while we show that there is no hope to achieve analogous results for the corresponding vertex or edge deletion versions. Our algorithms are based on transforming graph completion problems into efficiently solvable number problems and exploiting f-factor computations for translating the results back into the graph setting. Our core observation is that we encounter a win-win situation: either the number of edge additions is small or the problem is polynomial-time solvable. This approach helps in answering an open question by Mathieson and Szeider JCSS 2012 concerning the polynomial kernelizability of Degree Constraint Edge Addition and leads to a general method of approaching polynomial-time preprocessing for a wider class of degree sequence completion problems. We describe interactions between number and graph problems.f-Factor computations allow to link number and graph problems.We present a win-win kernelization framework for edge insertion problems.Maximum vertex degree governs the complexity of degree sequence completion problems.

References

[1]

C. Bazgan, R. Bredereck, S. Hartung, A. Nichterlein, G.J. Woeginger, Finding large degree-anonymous subgraphs is hard, Theor. Comput. Sci., 622 (2016) 90-110.

Digital Library

[2]

H.L. Bodlaender, F.V. Fomin, D. Lokshtanov, E. Penninkx, S. Saurabh, D.M. Thilikos, (Meta) kernelization, in: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2009, pp. 629-638.

[3]

H.L. Bodlaender, S. Thomassé, A. Yeo, Kernel bounds for disjoint cycles and disjoint paths, Theor. Comput. Sci., 412 (2011) 4570-4578.

Digital Library

[4]

H.L. Bodlaender, B.M.P. Jansen, S. Kratsch, Kernelization lower bounds by cross-composition, SIAM J. Discrete Math., 28 (2014) 277-305.

[5]

A. Borri, T. Calamoneri, R. Petreschi, Recognition of unigraphs through superposition of graphs, J. Graph Algorithms Appl., 15 (2011) 323-343.

[6]

A. Brandstädt, V.B. Le, J.P. Spinrad, Graph Classes: a Survey, SIAM, 1999.

Digital Library

[7]

L. Cai, Fixed-parameter tractability of graph modification problems for hereditary properties, Inf. Process. Lett., 58 (1996) 171-176.

Digital Library

[8]

L. Cai, J. Chen, R.G. Downey, M.R. Fellows, Advice classes of parameterized tractability, Ann. Pure Appl. Logic, 84 (1997) 119-138.

[9]

G. Chartrand, L. Lesniak, C.M. Mynhardt, O.R. Oellermann, Degree uniform graphs, Ann. N.Y. Acad. Sci., 555 (1989) 122-132.

[10]

S. Chester, B. Kapron, G. Srivastava, S. Venkatesh, Complexity of social network anonymization, Soc. Netw. Anal. Min., 3 (2013) 151-166.

[11]

K.L. Clarkson, K. Liu, E. Terzi, Towards identity anonymization in social networks, in: Link Mining: Models, Algorithms, and Applications, Springer, 2010, pp. 359-385.

[12]

G. Cornuéjols, General factors of graphs, J. Comb. Theory, Ser. B, 45 (1988) 185-198.

Digital Library

[13]

R.G. Downey, M.R. Fellows, Fundamentals of Parameterized Complexity, Springer, 2013.

[14]

D. Eppstein, E.S. Spiro, The h-index of a graph and its application to dynamic subgraph statistics, J. Graph Algorithms Appl., 16 (2012) 543-567.

[15]

P. Erd's, T. Gallai, Graphs with prescribed degrees of vertices, Mat. Lapok, 11 (1960) 264-274.

[16]

M.R. Fellows, Blow-ups, win/win's, and crown rules: some new directions in FPT, in: LNCS, vol. 2880, Springer, 2003, pp. 1-12.

[17]

M.R. Fellows, J. Guo, H. Moser, R. Niedermeier, A generalization of Nemhauser and Trotter's local optimization theorem, J. Comput. Syst. Sci., 77 (2011) 1141-1158.

Digital Library

[18]

J. Flum, M. Grohe, Parameterized Complexity Theory, Springer, 2006.

[19]

M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.

Digital Library

[20]

P.A. Golovach, Editing to a connected graph of given degrees, in: LNCS, vol. 8635, Springer, 2014, pp. 324-335.

[21]

P.A. Golovach, Editing to a graph of given degrees, Theor. Comput. Sci., 591 (2015) 72-84.

Digital Library

[22]

J. Guo, R. Niedermeier, Invitation to data reduction and problem kernelization, ACM SIGACT News, 38 (2007) 31-45.

Digital Library

[23]

P.L. Hammer, B. Simeone, The splittance of a graph, Combinatorica, 1 (1981) 275-284.

[24]

P.L. Hammer, T. Ibaraki, B. Simeone, Degree sequences of threshold graphs, Congr. Numer., 21 (1975) 329-355.

[25]

S. Hartung, C. Hoffmann, A. Nichterlein, Improved upper and lower bound heuristics for degree anonymization in social networks, in: LNCS, vol. 8504, Springer, 2014, pp. 376-387.

[26]

S. Hartung, A. Nichterlein, R. Niedermeier, O. Suchý, A refined complexity analysis of degree anonymization in graphs, Inf. Comput., 243 (2015) 249-262.

Digital Library

[27]

P. Katerinis, N. Tsikopoulos, Minimum degree and f-factors in graphs, N.Z. J. Math., 29 (2000) 33-40.

[28]

D.J. Kleitman, S.Y. Li, A note on unigraphic sequences, Stud. Appl. Math., 4 (1975) 283-287.

[29]

C. Komusiewicz, R. Niedermeier, New races in parameterized algorithmics, in: LNCS, vol. 7464, Springer, 2012, pp. 19-30.

[30]

S. Kratsch, Recent developments in kernelization: a survey, Bull. Eur. Assoc. Theor. Comput. Sci., 113 (2014).

[31]

K. Liu, E. Terzi, Towards identity anonymization on graphs, in: ACM SIGMOD Conference, ACM, 2008, pp. 93-106.

[32]

L. Lovász, M.D. Plummer, Matching Theory, North-Holland, 1986.

[33]

F. Maffray, M. Preissmann, Linear recognition of pseudo-split graphs, Discrete Appl. Math., 52 (1994) 307-312.

Digital Library

[34]

L. Mathieson, S. Szeider, Editing graphs to satisfy degree constraints: a parameterized approach, J. Comput. Syst. Sci., 78 (2012) 179-191.

Digital Library

[35]

H. Moser, D.M. Thilikos, Parameterized complexity of finding regular induced subgraphs, J. Discret. Algorithms, 7 (2009) 181-190.

Digital Library

[36]

A. Natanzon, R. Shamir, R. Sharan, Complexity classification of some edge modification problems, Discrete Appl. Math., 113 (2001) 109-128.

[37]

R. Niedermeier, Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.

Cited By

Bredereck RFroese VKoseler MGarlet Millani MNichterlein ANiedermeier R(2019)A Parameterized Algorithmics Framework for Degree Sequence Completion Problems in Directed GraphsAlgorithmica10.1007/s00453-018-0494-681:4(1584-1614)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s00453-018-0494-6
Dabrowski KGolovach Pvan 't Hof PPaulusma DThilikos D(2017)Editing to a planar graph of given degreesJournal of Computer and System Sciences10.1016/j.jcss.2016.11.00985:C(168-182)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1016/j.jcss.2016.11.009
Komusiewicz CNichterlein ANiedermeier R(2015)Parameterized Algorithmics for Graph Modification ProblemsRevised Papers of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science - Volume 922410.1007/978-3-662-53174-7_1(3-15)Online publication date: 17-Jun-2015
https://dl.acm.org/doi/10.1007/978-3-662-53174-7_1

Win-win kernelization for degree sequence completion problems
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

Kernelization of packing problems
SODA '12: Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms

Kernelization algorithms are polynomial-time reductions from a problem to itself that guarantee their output to have a size not exceeding some bound. For example, d-Set Matching for integers d ≥ 3 is the problem of finding a matching of size at least k ...
Burn and Win
Combinatorial Algorithms
Abstract
Given a graph G and an integer k, the Graph Burning problem asks whether the graph G can be burned in at most k rounds. Graph burning is a model for information spreading in a network, where we study how fast the information spreads in the network ...
Finding large degree-anonymous subgraphs is hard

A graph is said to be k-anonymous for an integer k, if for every vertex in the graph there are at least k - 1 other vertices with the same degree. We examine the computational complexity of making a given undirected graph k-anonymous either through at ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences

Journal of Computer and System Sciences Volume 82, Issue 6

September 2016

204 pages

ISSN:0022-0000

Issue’s Table of Contents

Copyright © Elsevier Inc.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 September 2016

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bredereck RFroese VKoseler MGarlet Millani MNichterlein ANiedermeier R(2019)A Parameterized Algorithmics Framework for Degree Sequence Completion Problems in Directed GraphsAlgorithmica10.1007/s00453-018-0494-681:4(1584-1614)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s00453-018-0494-6
Dabrowski KGolovach Pvan 't Hof PPaulusma DThilikos D(2017)Editing to a planar graph of given degreesJournal of Computer and System Sciences10.1016/j.jcss.2016.11.00985:C(168-182)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1016/j.jcss.2016.11.009
Komusiewicz CNichterlein ANiedermeier R(2015)Parameterized Algorithmics for Graph Modification ProblemsRevised Papers of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science - Volume 922410.1007/978-3-662-53174-7_1(3-15)Online publication date: 17-Jun-2015
https://dl.acm.org/doi/10.1007/978-3-662-53174-7_1

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents