Open Problems at PC301

Status
Working
Title
Date
Excerpt
Published
Tags
Feature on homepage
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:
  1. Does this problem have a subexponential-time algorithm on planar graphs?
  1. 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 literals
🛠
Parameter:
🤔
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 ?
  1. OPEN: Is this FPT?
  1. Also OPEN: For , P v/s NP
  1. Variation: Longest Path above Diameter, i.e, does there exist a path whose length is at least ?
  1. 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?
  1. Does this have a subquadratic, i.e, -sized, vertex kernel?
  1. KNOWN: Lower bound for instance kernel
  1. 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?
  1. Does this have a subquadratic, i.e, -sized, vertex kernel?
  1. KNOWN: Quadratic instance kernel
Kernel for Interval Completion (Saket Saurabh)
📌
Input:
🛠
Parameter:
🤔
Can we add edges to so that it becomes an interval graph?
  1. Does this have a
  1. 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?
  1. KNOWN: algorithms
  1. 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
  1. Weighted Cut in Digraphs
  1. Weighted DFVS
  1. Directed Multicut in Digraphs with three requests
  1. Terrain Guarding
  1. Directed Cut-width, Directed Path-width
Kernelization
  1. DFVS
  1. Planar Vertex Deletion
  1. Kernel for Rectangle Stabbing
  1. Kernel for Partial vertex cover on graph classes such as Bipartite or Planar Graphs
  1. Kernel for Bipartite Compression
  1. Lossy Kernel for Hole Packing / Minor Packing {even when F contains planar graph}
FPT Approximation
  1. Inapproximability of Cliques via FPT not equal to W[1]
  1. Does DFVS has (1+e) approx running in time (1/eps)^k for DFVS, Multicut
  1. Does Chordal Vertex Deletion or Planar Vertex Deletion have constant factor approximation in time?
  1. Approximation for Treedepth in c^tdepth time
Other
  1. Does Above Guarantee Vertex Cover (AGVC) have subexpontial algorithm on planar graphs?
  1. Single exponential lower bound for treewidth?