Structural graph properties vs proof hardness

  • Date October 18, 2018
  • Hour 3 pm
  • Room GSSI Library
  • Speaker Nicola Galesi (Roma "La Sapienza")
  • Area Computer Science


We present some recent results  showing how the hardness of proving a parity combinatorial principle on graphs (so-called Tseitin Principle)  is a function of well-known graph structural measures like tree-width, path-width, etc. The results entail characterizations  of  several proof measures in terms of well-known  graph searching games.