Current Trends in Exponential Time Algorithms (Ph.D. Course)

Ph.D. Course at ITU Copenhagen in exponential time algorithms, including parameterised computation.

When: We meet Thursdays at 10 AM, starting 3 March 2011.

Who: This course is organised by Thore Husfeldt, ITU and aimed at Ph.D. students and advanced graduate students. Send Thore an email if you plan to attend or have questions.

Format: Weekly meetings (1-2 hours) of informal seminar-style presentation of selected recent papers. Participants are encouraged to discuss their own research, including open problems, partial progress, and half-baked results. 10-12 meetings during the Spring term 2011.

Prerequisites: This is a research-level course. Prerequisites correspond roughly to the monograph F. Fomin and D. Kratsch, Exact Exponential Algorithms, Springer 2010.

ECTS: Active participation in this course yields 2.5 ECTS.


  • 3 Mar at 11 AM in 4A05: Konstantin Kutzkov about bicliques. Relevant papers:
    1. Reduction between Maximum Frequent Itemsets(k1, k2) and Biclique(k1, k2): Gunopulos, D., Khardon, R., Mannila, H., Saluja, S., Toivonen, H., Sharm, R.S.:
      Discovering all most specific sentences. ACM Trans. Database Syst. 28(2), 140–174
    2. Biclique(k1, k2) is NP-complete: David Johnson, The NP-Completeness Column: An Ongoing Guide, J.Algorithms, 1987
    3. Inapproximability of Biclique(k1, k2): Khot, S.: Ruling out ptas for graph min-bisection, densest subgraph and bipartite clique. In: FOCS, pp. 136–145 (2004)
    4. Biclique(k1, k2): In FPT or W[1]-hard: Open Problems from Dagstuhl Seminar 07281:
      ( page 4: The problems proposed by Mike Fellows and Daniel Marx.
    5. A parameterized algorithm for Bipartite VC: H. Fernau and R. Niedermeier. An efficient exact algorithm for constraint bipartite vertex cover. Journal of Algorithms, 38(2):374–410, 2001.
    6. Exact non-parameterized algorithm for Biclique(k1, k2): Daniel Binkele-Raible, Henning Fernau, Serge Gaspers, Mathieu Liedloff: Exact exponential-time algorithms for finding bicliques.
      Inf. Process. Lett. 111(2): 64-67 (2010)
    7. The paper showing that Minimum Infrequent Set is W[2]-hard: Mario Boley. On Approximating Minimum Infrequent and Maximum Frequent Sets. Discovery Science, page 68-77. 2007 (Section 2)
  • 10 Mar at 10AM, in 409: Thore Husfeldt presents Imagliazzo, Paturi: On the Complexity of k-SAT. J. Comput. Syst. Sci. 62(2): 367-375 (2001). [PDF]. (note change!)
  • 17 Mar at 11AM, in 4A05: Nina Taslaman presents Calabro et al.: On the Exact Complexity of Evaluating Quantified k-CNF. From proceedings of IPEC 2010
  • 24 Mar at 11AM, in 4A09: Andreas Björklund on Hamiltonicity detection in cubic graphs.
  • 31 Mar at 10AM, in 4A09: Thore Husfeldt on algorithms for the permanent, based on arxiv0904.3251 (also Inf. Process. Lett. 110(20): 867-870 (2010)).
  • 7 April at 10AM, in XXXX: Natalie Schluter presents (part of) Golovach et al.: Colorings with Few Colors: Counting, Enumeration and Cominatorial Bounds.  From proceedings of WG 2010.
  • 14 April at 11AM, in XXXX: Thore Husfeldt presents Kawarabayashi’s paper on an algorithm for the k-cycle problem.
  • 28 April at 10AM, in 4A05: Natalie Schluter presents Grigni: A Sperner Lemma Complete for PPA.  In Information Processing Letters, 77(5-6): 255-259 (2001).
  • 5 May at 10AM in 2A05: Søren Bøg presents “Planning over chain causal graphs for variables with domains of size 5 Is NP-hard” af O. Giménez og A. Jonsson, abstract.
  • 12 May: No meeting
  • 19 May, 11 AM in 4A05: Thore Husfeldt presents arxiv1103.0534.

0 Responses to “Current Trends in Exponential Time Algorithms (Ph.D. Course)”

  1. No Comments

Leave a Reply

You must login to post a comment.