Gregory Gutin - Selected Publications#

[1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Application, 2nd Ed, 2009; 1st Ed. (2000) was published in Chinese in 2009 and 2nd Ed. is to be published in Chinese by Beijing World Publishing Corp.

[2] G. Gutin, M. Wahlstrom, and A. Yeo, Rural postman parameterized by the number of components of required edges. Journal of Computer and System Sciences 83(1) 2017, 121-131. The authors solved “a more than thirty years open... question with significant practical relevance” (Sorge et al., Lect. Notes Comput. Sci., vol.7056, 2011, pp.310-322). Results of this paper and [3-4]] below were already discussed in R. van Bevern, R. Niedermeier, M. Sorge, and M. Weller. Complexity of arc routing problems. Chapter 2 in Arc Routing: Problems, Methods, and Applications, SIAM, 2014 and used by Golovnev et al., Inf. Process. Lett. 114(8) (2014) 421–425 to resolve an open problem on the Shortest Common Superstring problem.

[3] G. Gutin, M. Jones and B. Sheng, Parameterized Complexity of the k-Arc Chinese Postman Problem. Journal of Computer and System Sciences 84C (2017) 107-119.

[4] G. Gutin, M. Jones, and M. Wahlstrom, The Mixed Chinese Postman Problem Parameterized by Pathwidth and Treedepth. SIAM Journal on Discrete Mathematics 30(4) (2016) 2177-2205.

[5] R. Crowston, M. Fellows, G. Gutin, M. Jones, E.J. Kim, F. Rosamond, I.Z. Ruzsa, S.Thomasse, and A. Yeo, Satisfying More Than Half of a System of Linear Equations Over GF(2): A Multivariate Approach. Journal of Computer and System Sciences 80 (2014) 687-696. A new linear algebra based method was introduced. Using it an open problem of Mahajan et al. (IWPEC 2006, JCSS 2009) was solved.

[6] J. Crampton, G. Gutin and A. Yeo, On the Parameterized Complexity and Kernelization of the Workflow Satisfiability Problem. ACM Transactions on Information and System Security16 (2013), article no. 4. 32 citations.

[7] D. Cohen, J. Crampton, A. Gagarin, G. Gutin and M. Jones, Iterative Plan Construction for the Workflow Satisfiability Problem. Journal of Artificial Intelligence Research 51 (2014), 555-577. 20 citations.

The last two papers were the first to introduce wide classes of constraints which include many practical access control constraints. The papers designed theoretically efficient algorithms. Later papers evaluated implementations of the algorithmic approach of [7]] and showed its clear superiority over the previous state-of-the-art practical algorithms for the Workflow Satisfiability Problem.

[8] J. Crampton, G. Gutin and D. Karapetyan, Valued Workflow Satisfiability Problem. In 20th ACM SACMAT (2015), 3-13. 9 citations. Best paper award.

[9] G. Gutin, E.J. Kim, S. Szeider, and A. Yeo, A Probabilistic Approach to Problems Parameterized

Above or Below Tight Bounds. Journal of Computer and System Sciences 77 (2011), 422-429. 39 citations.

[10] N. Alon, G. Gutin, E.J. Kim, S. Szeider, and A. Yeo, Solving MAX-k-SAT Above a Tight Lower Bound. Algorithmica, 61 (2011), 638-655. 88 citations.

The last two papers introduced a new method for designing fixed-parameter tractable algorithms for constraint satisfaction problems. Prior to these papers there was no approach for solving several open problems stated in Mahajan et al. (IWPEC 2006, JCSS 2009) and Niedermeier (Invitation to Fixed-Parameter Algorithms, OU Press, 2006). The use of the new method allowed researchers to solve most of these problems. The two papers also led to a wider use of probabilistic method in parameterized algorithmics.