DFG Project ITKO: Iterative Compression for Solving Hard Network Problems

Project Description

The technique of “iterative compression” recently suggested by Reed, Smith, and Vetta provides a new tool for the design of exact algorithms for combinatorial complex network problems. The project ITKO aims to investigate the theoretical foundations of iterative compression and to explore and extend its range of application. In particular the (improved) method is to be applied to a list of concretely suggested network problems to obtain new efficient algorithms. Last but not least an objective is to implement and and test the thus gained algorithms in a practical environment. First experiences of the working group in handling iterative compression are very promising.

People

Hannes Moser Dipl.-Inform., Researcher Room 3323 Phone: (+49) 3641 9 46324

• Michael Dom
• Jiong Guo (DFG-Project PIAF)
• Falk Hüffner (DFG-Project PIAF)
• Sebastian Wernicke

Publications

• Falk Hüffner, Christian Komusiewicz, Hannes Moser, and Rolf Niedermeier:
  Fixed-parameter algorithms for cluster vertex deletion.
  In Proceedings of the 8th Latin American Theoretical Informatics Symposium (LATIN'08), Búzios, Brazil. April 2008.
  Lecture Notes in Computer Science, Springer.
• Falk Hüffner, Nadja Betzler, and Rolf Niedermeier:
  Optimal edge deletions for signed graph balancing.
  In Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07), Rome, Italy. June 2007.
  Volume 4525 in Lecture Notes in Computer Science, pages 297–310, Springer.

Software

• The Balanced Subgraph solver “bsg” based on iterative compression.

Related Work of the Group

Publications

• Michael Dom, Jiong Guo, Falk Hüffner, Rolf Niedermeier, and Anke Truß:
  Fixed-parameter tractability results for feedback set problems in tournaments.
  In Proceedings of the 6th Conference on Algorithms and Complexity (CIAC'06), Rome, Italy. May 2006.
  Volume 3998 in Lecture Notes in Computer Science, pages 320–331, Springer (original publication).
• Jiong Guo, Jens Gramm, Falk Hüffner, Rolf Niedermeier, and Sebastian Wernicke:
  Compression-based fixed-parameter algorithms for Feedback Vertex Set and Edge Bipartization.
  Journal of Computer and System Sciences, 72(8): 1386–1396, 2006 (original publication).
• Falk Hüffner:
  Algorithm engineering for optimal graph bipartization.
  In Proceedings of the 4th International Workshop on Efficient and Experimental Algorithms (WEA'05), Santorini Island, Greece. May 2005.
  Volume 3503 in Lecture Notes in Computer Science, pages 240–252, Springer (original publication). Journal version in preparation.
  
  

Software

• The Graph Bipartization solver “occ” based on iterative compression.