Gyula Pap

Postdoctoral Researcher, Egerváry Research Group (EGRES)

email:



Hallgatóknak: Kombinatorikus Algoritmusok Gyakorlat 2014

 

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.

I like sports with rackets, including tennis, badminton, ping-pong, squash, despite losing most of the time. I am proud of my famous past achievments such as completing a marathon in 3:44, and - on a different day - completing a half-marathon in 1:32, and completing the expert level of the ancient windows game minesweeper in 47 seconds. Twice I won a gold medal at the international mathematics olympiad. My favorite TV show is the cartoon Family Guy. With my wife Olga, we have a daughter called Lola, she's , and two sons named Kende and Márkó, they're .

Curriculum vitae and list of publications.

Selected papers:


Combinatorial algorithms for matchings, even factors and square-free 2-factors, Mathematical Programming Ser. B, Volume 110, Issue 1, (March 2007), 57-69. PS

In this paper I constructed a combinatorial algorithm to solve matching type problems. The point is that concepts of well-known matching algorithms fail with even factors and square-free 2-factors. A polynomial time algorithm for these problems has been known before, but were more involved than should be. Instead, I modified Edmonds' original non-bipartite matching algorithm so that it works for even factors and square free 2-factors. 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 non-returning A-paths, Combinatorica, Volume 27, Issue 2, (March 2007), 247-251. PS

I prove a min-max formula for the maximum number of disjoint non-returning A-paths. 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 min-max 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), 167-181. 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 parity-constrained rooted k-arc-connected 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) 201-213. PDF

Laci Szegő was my diploma advisor, and we proved this min-max result on even factors as a follow-up of our work on path-matching 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 NP-complete, 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 non-bipartite matching.


Weighted Restricted 2-Matching, Mathematical Programming, Ser. B, (2008). PDF

This is my favorite paper. Among others special cases I prove that, given an edge-weighted graph, one can find in strongly polynomial time a minimum weight perfect 2-matching without a triangle or a pentagon.


Mader matroids are gammoids, EGRES TR-2006-17. 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 A-paths", 5th Japanese-Hungarian 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