Document Open Access Logo

A Parameterized Algorithmics Framework for Degree Sequence Completion Problems in Directed Graphs

Authors Robert Bredereck, Vincent Froese, Marcel Koseler, Marcelo Garlet Millani, André Nichterlein, Rolf Niedermeier

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2016.10.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Robert Bredereck
Vincent Froese
Marcel Koseler
Marcelo Garlet Millani
André Nichterlein
Rolf Niedermeier

Cite As Get BibTex

Robert Bredereck, Vincent Froese, Marcel Koseler, Marcelo Garlet Millani, André Nichterlein, and Rolf Niedermeier. A Parameterized Algorithmics Framework for Degree Sequence Completion Problems in Directed Graphs. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.IPEC.2016.10

Abstract

There has been intensive work on the parameterized complexity of the typically NP-hard task to edit undirected graphs into graphs fulfilling certain given vertex degree constraints. In this work, we lift the investigations to the case of directed graphs; herein, we focus on arc insertions. To this end, our general two-stage framework consists of efficiently solving a problem-specific number problem transferring its solution to a solution for the graph problem by applying flow computations. In this way, we obtain fixed-parameter tractability and polynomial kernelizability results, with the central parameter being the maximum vertex in- or outdegree of the output digraph. Although there are certain similarities with the much better studied undirected case, the flow computation used in the directed case seems not to work for the undirected case while f-factor computations as used in the undirected case seem not to work for the directed case.

Subject Classification

Keywords
  • NP-hard graph problem
  • graph realizability
  • graph modification
  • arc insertion
  • fixed-parameter tractability
  • kernelization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Jørgen Bang-Jensen, András Frank, and Bill Jackson. Preserving and increasing local edge-connectivity in mixed graphs. SIAM Journal on Discrete Mathematics, 8(2):155-178, 1995. Google Scholar
  2. Jørgen Bang-Jensen, Jing Huang, and Xuding Zhu. Completing orientations of partially oriented graphs. CoRR abs/1509.01301, 2015. Google Scholar
  3. Cristina Bazgan, Robert Bredereck, Sepp Hartung, André Nichterlein, and Gerhard J. Woeginger. Finding large degree-anonymous subgraphs is hard. Theoretical Computer Science, 622:90-110, 2016. Google Scholar
  4. Jordi Casas-Roma, Jordi Herrera-Joancomartí, and Vicenç Torra. An algorithm for k-degree anonymity on large networks. In Proceedings of the International Conference on Advances in Social Networks Analysis and Mining (ASONAM'13), pages 671-675. ACM, 2013. Google Scholar
  5. Sean Chester, Bruce Kapron, Gautam Srivastava, and S. Venkatesh. Complexity of social network anonymization. Social Network Analysis and Mining, 3(2):151-166, 2013. Google Scholar
  6. Marek Cygan, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Ildikó Schlotter. Parameterized complexity of eulerian deletion problems. Algorithmica, 68(1):41-61, 2014. Google Scholar
  7. Frederic Dorn, Hannes Moser, Rolf Niedermeier, and Mathias Weller. Efficient algorithms for eulerian extension and rural postman. SIAM Journal on Discrete Mathematics, 27(1):75-94, 2013. Google Scholar
  8. Vincent Froese, André Nichterlein, and Rolf Niedermeier. Win-win kernelization for degree sequence completion problems. Journal of Computer and System Sciences, 82(6):1100-1111, 2016. Google Scholar
  9. D. Gale. A theorem on flows in networks. Pacific Journal of Mathematics, 7:1073-1082, 1957. Google Scholar
  10. Petr A. Golovach. Editing to a graph of given degrees. Theoretical Computer Science, 591:72-84, 2015. Google Scholar
  11. Petr A. Golovach and George B. Mertzios. Graph editing to a given degree sequence. In Proceedings of the 11th International Computer Science Symposium in Russia (CSR'16), volume 9691 of LNCS, pages 177-191. Springer, 2016. Google Scholar
  12. Gregory Gutin and Anders Yeo. Some parameterized problems on digraphs. Computer Journal, 51(3):363-371, 2008. Google Scholar
  13. Sepp Hartung, Clemens Hoffmann, and André Nichterlein. Improved upper and lower bound heuristics for degree anonymization in social networks. In Proceedings of the 13th International Symposium on Experimental Algorithms (SEA'14), volume 8504 of LNCS, pages 376-387. Springer, 2014. Google Scholar
  14. Sepp Hartung, André Nichterlein, Rolf Niedermeier, and Ondřej Suchý. A refined complexity analysis of degree anonymization in graphs. Information and Computation, 243:249-262, 2015. Google Scholar
  15. Marcel Koseler. Kernelization for degree-constraint editing on directed graphs. Bachelor thesis, TU Berlin, November 2015. URL: http://fpt.akt.tu-berlin.de/publications/theses/BA-marcel-koseler.pdf.
  16. Hendrik W. Lenstra. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8:538-548, 1983. Google Scholar
  17. Kun Liu and Evimaria Terzi. Towards identity anonymization on graphs. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD'08, pages 93-106. ACM, 2008. Google Scholar
  18. Luke Mathieson and Stefan Szeider. Editing graphs to satisfy degree constraints: A parameterized approach. Journal of Computer and System Sciences, 78(1):179-191, 2012. Google Scholar
  19. Marcelo Garlet Millani. Algorithms and complexity for degree anonymization in directed graphs. Bachelor thesis, TU Berlin, March 2015. URL: http://fpt.akt.tu-berlin.de/publications/theses/BA-marcelo-millani.pdf.
  20. Hannes Moser and Dimitrios M. Thilikos. Parameterized complexity of finding regular induced subgraphs. Journal of Discrete Algorithms, 7(2):181-190, 2009. Google Scholar
  21. James B. Orlin. Max flows in o(nm) time, or better. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC'13), pages 765-774. ACM, 2013. Google Scholar
  22. Mathias Weller, Christian Komusiewicz, Rolf Niedermeier, and Johannes Uhlmann. On making directed graphs transitive. Journal of Computer and System Sciences, 78(2):559-574, 2012. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact