## Counting OCTs (Saket Saurabh)

In the context of an undirected graph , an OCT (odd cycle transversal) a subset such that is bipartite.

Input:

Parameter:

Can we count all OCTs of of size at most in time?

## Above Guarantee Vertex Cover (Saket Saurabh)

Input:

Parameter: , where is the size of the maximum matching of .

Does have a vertex cover of size at most ?

What is known: on general graphs, where .

Open problems:

- Does this problem have a subexponential-time algorithm on planar graphs?

- Deterministic polynomial kernel on planar graphs?

## Weighted -CUT (Saket Saurabh)

Input: , where is a directed graph

Parameter:

Find a cut of size of minimum weight.

Interesting consquences include implications for DFVS.

## Dual Parameterization of Edge Deletion to Cluster Graphs (Petr Golovach)

Input:

Parameter: , where is the size of the maximum matching of .

Can we delete a subset at most edges sp that is a cluster graph?

## FPT-Approximation for -SAT (Saket Saurabh, Venkatesh Raman, Karthik C.S.)

Input: where is a CNFSAT instance where every clause has

*exactly*three literalsParameter:

Does there exist an algorithm FPT in that satisfies at least clauses?

## Directed Path above Shortest Path (Fedor Fomin)

Input: where is a directed graph

Parameter:

Does there exist a path whose length is at least ?

- OPEN: Is this FPT?

- Also OPEN: For , P v/s NP

- Variation: Longest Path above Diameter, i.e, does there exist a path whose length is at least ?

- Known to be FPT for undirected graphs.

## Kernel for Split Vertex Deletion (Akanksha Agrawal)

Input:

Parameter:

Does have a subset of at most vertices such that is a split graph?

- Does this have a subquadratic, i.e, -sized, vertex kernel?

- KNOWN: Lower bound for instance kernel

- Similar question: Subset-FVS on split graphs

## Kernel for Chordal Completion (Ashutosh Rai)

Input:

Parameter:

Can we add edges to so that it becomes chordal?

- Does this have a subquadratic, i.e, -sized, vertex kernel?

- KNOWN: Quadratic instance kernel

## Kernel for Interval Completion (Saket Saurabh)

Input:

Parameter:

Can we add edges to so that it becomes an interval graph?

- Does this have a

- KNOWN: Quadratic instance kernel

## Coloring on -free graphs (Petr Golovach)

Input: , where is a -free graph, which are graphs that exclude paths on five vertices as induced subgraphs

Parameter:

Is -colorable?

- KNOWN: algorithms

- Also KNOWN: For -free graphs the situation is well-understood (chordal graphs)

**Other Problems not discussed during the session (Saket Saurabh)**

## Old Classical FPT versus W[1]-Hard

- Weighted Cut in Digraphs

- Weighted DFVS

- Directed Multicut in Digraphs with three requests

- Terrain Guarding

- Directed Cut-width, Directed Path-width

## Kernelization

- DFVS

- Planar Vertex Deletion

- Kernel for Rectangle Stabbing

- Kernel for Partial vertex cover on graph classes such as Bipartite or Planar Graphs

- Kernel for Bipartite Compression

- Lossy Kernel for Hole Packing / Minor Packing {even when F contains planar graph}

## FPT Approximation

- Inapproximability of Cliques via FPT not equal to W[1]

- Does DFVS has (1+e) approx running in time (1/eps)^k for DFVS, Multicut

- Does Chordal Vertex Deletion or Planar Vertex Deletion have constant factor approximation in time?

- Approximation for Treedepth in c^tdepth time

## Other

- Does Above Guarantee Vertex Cover (AGVC) have subexpontial algorithm on planar graphs?

- Single exponential lower bound for treewidth?