Gyula PapPostdoctoral Researcher, Egerváry Research Group (EGRES) email:


I am a research fellow at Egerváry
Research Group on Combinatorial Optimization, lead by
Professor András Frank. My focus is on combinatorial
optimization, graph theory, matching, matroids and polyhedra. 
Curriculum vitae and list of publications.
Selected papers:
Combinatorial algorithms for matchings, even factors and squarefree 2factors, Mathematical Programming Ser. B, Volume 110, Issue 1, (March 2007), 5769. PS In this paper I constructed a combinatorial algorithm to solve matching type problems. The point is that concepts of wellknown matching algorithms fail with even factors and squarefree 2factors. A polynomial time algorithm for these problems has been known before, but were more involved than should be. Instead, I modified Edmonds' original nonbipartite matching algorithm so that it works for even factors and square free 2factors. These results have been cited by Harvey's paper on its algebraic aspects, three papers of Takazawa on the weighted version, and Iwata and Takazawa's SODA paper on a matroidal extension. 
Packing nonreturning Apaths, Combinatorica, Volume 27, Issue 2, (March 2007), 247251. PS I prove a minmax formula for the maximum number of disjoint nonreturning Apaths. This generalizes a result of Chudnovsky, Geelen, Gerards, Goddyn, Lohman, Seymour. My proof is shorter then theirs, which I found by carefully looking at Lex Schijver's proof for Mader's minmax formula. 
(with Márton Makai, Jácint Szabó) Matching Problems in Polymatroids Without Double Circuits, IPCO XII, 2007, Ithaca NY, [in: Integer Prog. and Comb. Opt., M. Fischetti, D.P. Williamson eds.], Lecture Notes in Computer Science 4513, Springer (2007), 167181. PDF In this paper we consider a certain class of matroid matching problems, and prove that a condition defined by a partition is necessary and sufficient. Special cases are parityconstrained rooted karcconnected orientations of a graph, and the maximum genus embedding of a graph. My contribution is a strongly polynomial time algorithm to find a maximum matching in a polymatroid without double circuits and the partition certifying its maximality. 
(with László Szegő) On the maximum even factor in weakly symmetric graphs, Journal of Combinatorial Theory Ser. B, 91/2 (2004) 201213. PDF Laci Szegő was my diploma advisor, and we proved this minmax result on even factors as a followup of our work on pathmatching for my master's thesis. A perfect even factor in a digraph is the union of disjoint cycles of even length. The existence of a perfect even factor is NPcomplete, but on the other hand, Cunningham and Geelen proved that it is polynomial time solvable for weakly symmetric digraphs, i.e. those graph where all strong components are symmetric. Our contribution is a simplified characterization, which actually generalizes Tutte's theorem on nonbipartite matching. 
Weighted Restricted 2Matching, Mathematical Programming, Ser. B, (2008). PDF This is my favorite paper. Among others special cases I prove that, given an edgeweighted graph, one can find in strongly polynomial time a minimum weight perfect 2matching without a triangle or a pentagon. 
Mader matroids are gammoids, EGRES TR200617. PS Lex Schrijver, in his book, asked the open question "Is every Mader matroid a gammoid?" I proved that the answer is a mere "Yes". The proof relies on Mader's formula, and is motivated by the structural results of Sebő and Szegő. 
Invited talks:
"A survey of results on packing Apaths", 5th
JapaneseHungarian Symposium on Discrete Mathematics and its
Applications, 2007, Sendai, Japan. slides
"A new approach to alternating paths", The
Hungarian Method is Fifty, 2005, the Hungarian Academy of Sciences,
Budapest, Hungary. slides