Combinatorial problems with an emphasis on games  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
116095
Type SNN
Principal investigator Tuza, Zsolt
Title in Hungarian Kombinatorikus problémák középpontban a játékokkal
Title in English Combinatorial problems with an emphasis on games
Keywords in Hungarian dominálási játék, szaturáló játék, ládapakolási játék, gráfok és hipergráfok dominálása
Keywords in English domination game, saturation game, bin-packing game, domination of graphs and hypergraphs
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Discrete mathematics
Panel Mathematics and Computing Science
Department or equivalent Alfréd Rényi Institute of Mathematics, HAS
Participants Bujtás, Csilla
Dósa, György
Patkós, Balázs
Vizer, Máté
Starting date 2015-09-01
Closing date 2019-02-28
Funding (in million HUF) 24.912
FTE (full time equivalent) 8.58
state running project





 

Final report

 
Results in Hungarian
A projekt fő kutatási témáját a gráfdominálási problémák és a kombinatorikus játékok alkották. Eredményes együttműködést alakítottunk ki a szlovén csoporttal. Elindítottuk a Grundy-típusú dominálási sorozatok szisztematikus vizsgálatát és bevezettük a kapcsolódó dominálási játékokat. Új technikákat dolgoztunk ki, továbbá kimutattuk az egyik változatnak a zéró-forszolási problémával való ekvivalenciáját. Definiáltuk a hipergráfok transzverzális-játékát, ami egy magasabb szinten modellez többféle gráfdominálási játékot. Éles felső korlátot bizonyítottunk a megfelelő hipergráf-paraméterre; ily módon a totális dominálási játékra vonatkozó 3/4-sejtést is bebizonyítottuk elsőfokú csúcsot nem tartalmazó gráfokra. Az 1980-as évekből eredő "Majority" probléma kapcsán - ami bizonyos protokoll szerint azt kívánja eldönteni, hogy egy halmazban mely típusú tárgyból van a legtöbb - általánosításokat vizsgáltunk és korábbról ismert eredményeknél erősebbeket értünk el. Önző ládapakolási játékokban a tárgyak valamilyen szabály szerint osztoznak a ládájuk a költségén. Egy tárgy áthelyezhető, ha így csökkenti saját költségét. A végállapotok (Nash ekvilibrium) maximális ládaszámának és az elhelyezés legkisebb elérhető helyigényének hányadosára többféle szabály mellett adtunk becsléseket. A projekt során 72 publikációnk készült, legalább kétharmaduk impakt faktoros SCI folyóiratcikk. A második futamévben workshopot is szerveztünk, ami szintén új tudományos eredményekre vezetett.
Results in English
The main part of the project consisted in graph domination problems and combinatorial games. We established fruitful collaboration with the Slovene group. We initiated the systematic study of Grundy-type domination sequences and introduced corresponding versions of the domination game. We developed new techniques, moreover pointed out the equivalence of one version with the zero-forcing problem. We introduced the general model called transversal game, played on hypergraphs. It can model various domination games played on graphs. We gave a sharp general upper bound on the parameter called game transversal number; this way we also proved the 3/4-conjecture on the total domination game for graphs of minimum degree at least 2. Concerning the Majority Problem raised in the 1980s - whose goal is to decide under a certain protocol, which type of items occurs most often in a set - we studied generalizations and achieved results stronger than the earlier known ones. In Selfish Bin Packing Games the items share the cost of their bin according to some rule. An item may move to another bin if this decreases its own cost. Under various rules we gave estimates on the ratio of the largest number of bins in a final position (Nash equilibrium) and the smallest achievable number of bins. During the project we wrote 72 publications, at least 2/3 of them in SCI journals with impact factor. In the second year we also organized a workshop, it lead to further new scientific results.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=116095
Decision
Yes





 

List of publications

 
G. Dosa, Zs. Tuza: Multiprofesor Scheduling, Discrete Applied Mathematics, 234, 195-209, 2018
G. Dosa, H. Kellerer, Zs. Tuza: Restricted assignment scheduling with resource constraints, Theoretical Computer Science, 760, 72-87, 2019
Cs. Bujtás, M. Jakovac: Relating the total domination number and the annihilation number of cactus cactus graphs and block graphs, Ars Mathematica Contemporanea 16:1 183-202, 2019
Zs. Tuza: Mixed hypergraphs and beyond, The Art of Discrete and Applied Mathematics, accepted, 2018
Gy. Dosa, L. Epstein: Quality of strong equilibria for selfish bin packing with uniform cost sharing, Journal of Scheduling, in print, DOI: 10.1007/s10951-018-0587-8, 2018
Gy. Dosa, L. Epstein: Pareto optimal equilibria for selfish bin packing with uniform cost sharing, Journal of Combinatorial Optimization, 37:3, 827-847, 2019
D. Gerbner, B. Patkós, M. Vizer: Forbidden subposet problems for traces of set families, Electronic Journal of Combinatorics, 25:3, P3.49, 2018
D. Gerbner, M. Vizer: Majority problems of large query size, Discrete Applied Mathematics, 254, 124-134, 2019
D. Gerbner, M.Vizer: Smart elements in combinatorial group testing problems with more defectives, The Art of Discrete and Applied Mathematics, accepted, 2017
D. Gerbner, D. Lenger, M. Vizer: A plurality problem with three colors and query size three, Proceedings of 11th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, accepted, 2017
D. Gerbner, B. Keszegh, A. Methuku, B. Patkós, M. Vizer: An improvement on the maximum number of k-dominating independent sets, Journal of Graph Theory, in print, DOI: 10.1002/jgt.22422, 2018
Cs. Bujtás, B. Patkós, Zs. Tuza, M. Vizer: Domination game on uniform hypergraphs, Discrete Applied Mathematics, 258, 65-75, 2019
B. Brešar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, T. Marc, B. Patkós, Zs. Tuza, M. Vizer: On Grundy total domination number in product graphs,, Discussiones Mathematicae Graph Theory, in print, DOI: 10.7151/dmgt.2184, 2018
Gy. Dósa, H. Kellerer, Zs. Tuza: Bin packing games with weight decision: how to get a small value for the Price of Anarchy, In: Epstein L., Erlebach T. (eds), Approximation and Online Algorithms. WAOA 2018, Lecture Notes in Computer Science, 11312, pp. 204-217, 2018
J. Balogh, J. Békési, Gy. Dósa, L. Epstein, A. Levin: Lower Bounds for Several Online Variants of Bin Packing, Theory of Computing Systems, in print, DOI: 10.1007/s00224-019-09915-1, 2019
J. Balogh, J. Békési, Gy. Dósa, J. Sgall, R. van Stee: The optimal absolute ratio for online bin packing, Journal of Computer and System Sciences, 102, 1-17, 2019
Gy. Dósa, A. Fügenschuh, Z. Tan, Zs. Tuza, K. Węsek: Tight lower bounds for semi-online scheduling on two uniform machines with known optimum, European Journal of Operations Research, in print, DOI: 10.1007/s10100-018-0536-9, 2018
R. B. Bapat, S. Fujita, S. Legay, Y. Manoussakis, Y. Matsui, T. Sakuma, Zs. Tuza: Safe sets, network majority on weighted trees, Networks. 71, 81-92., 2018
R. Águeda, N. Cohen, S. Fujita, S. Legay, Y. Manoussakis, Y. Matsui, L. Montero, R. Naserasr, H. Ono, Y. Otachi, T. Sakuma, Zs. Tuza, R. Xu: Safe sets in graphs: Graph classes and structural parameters, Journal of Combinatorial Optimization, 36:4, 1221-1242, 2018
G. Bacsó, D. Lokshtanov, D. Marx, M. Pilipczuk, Zs. Tuza, E. J. van Leeuwen: Subexponential-time algorithms for Maximum Independent Set in Pt-Free and broom-free graphs, Algorithmica, 81:2, 421–438, 2019
C. Bazgan, H. Fernau, Zs. Tuza: Aspects of upper defensive alliances, Discrete Applied Mathematics, in print, DOI: 10.1016/j.dam.2018.05.061, 2018
L. Badakhshian, G. O. H. Katona, Zs. Tuza: The domination number of the graph defined by two levels of the n-cube, Discrete Applied Mathematics, in print, DOI: 10.1016/j.dam.2019.02.006, 2019
C. Bazgan, T. Pontoizeau, Zs. Tuza: Finding a potential community in networks, Theoretical Computer Science, 769, 32-42, 2019
G. Bacsó, Cs. Bujtás, C. Tompkins, Zs. Tuza: Disjoint paired-dominating sets in cubic graphs, submitted manuscript, 2018
S. Cichacz, A. Görlich, Zs. Tuza: Z2xZ2-cordial cycle-free hypergraphs, submitted manuscript, 2018
M. Gionfriddo, L. Milazzo, Zs. Tuza: Hypercycle systems, submitted manuscript, 2018
Zs. Tuza: Graph labeling games, Electronic Notes in Discrete Mathematics, 60, 61-68, 2017
Cs. Bujtás, Zs. Tuza: Partition-crossing hypergraphs, Acta Cybernetica, 23:3, 815-828, 2018
G. Boruzanli Ekinci, Cs. Bujtás: On the equality of domination number and 2-domination number, submitted manuscript, 2018
D. Gerbner, B. Keszegh, A. Methuku, B. Patkós, M. Vizer: An improvement on the maximum number of k-dominating independent sets, submitted manuscript, 2017
Cs. Bujtás, B. Patkós, Zs. Tuza, M. Vizer: Domination game on uniform hypergraphs, submitted manuscript, 2017
D. Gerbner, A. Methuku, D. T. Nagy, B. Patkós, M. Vizer: Forbidding rank-preserving copies of a poset, submitted manuscript, 2017
B. Brešar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, T. Marc, B. Patkós, Zs. Tuza, M. Vizer: On Grundy total domination number in product graphs,, submitted manuscript, 2017
D. Gerbner, A. Methuku, D. T. Nagy, B. Patkós, M. Vizer: On the number of containments in P-free families, submitted manuscript, 2017
D. Gerbner, A. Methuku, D. Nagy, B. Patkós, M. Vizer: Stability results on vertex Turán problems in Kneser graphs, submitted manuscript, 2018
D. Gerbner, A. Methuku, D. T. Nagy, B. Patkós, M. Vizer: Vertex Turán problems for the oriented hypercube, submitted manuscript, 2018
E. Győri, D. Korándi, A. Methuku, I. Tomon, C. Tompkins, M. Vizer: On the Turán number of some ordered even cycles, European Journal of Combinatorics, 73, 81-88, 2018
E. Győri, A. Methuku, N. Salia, C. Tompkins, M. Vizer: On the maximum size of connected hypergraphs without a path of given length, Discrete Mathematics, 341:9, 2602-2605, 2018
D. Gerbner, A. Methuku, M. Vizer: Generalized Turán problems for disjoint copies of graphs, submitted manuscript, 2018
D. Gerbner, E. Győri, A. Methuku, M. Vizer: Generalized Turán problems for even cycles, submitted manuscript, 2018
G. Kiss, R. D. Malikiosis, G. Somlai, M. Vizer: On the discrete Fuglede and Pompeiu problems, submitted manuscript, 2018
D. Gerbner, A. Methuku, G. Omidi, M. Vizer: Ramsey problems for Berge hypergraphs, submitted manuscript, 2018
Gy. Dósa: The Intermediate Price of Anarchy (IPoA) in bin packing games, Discrete Applied Mathematics 242, 16-25, 2018
Gy. Dósa, L. Epstein: The tight asymptotic approximation ratio of First Fit for bin packing with cardinality constraints, Journal of Computer and System Sciences, 96, 33-49, 2018
Gy. Dósa, H. Kellerer, Zs. Tuza: Bin packing games with weight decision: how to get a small value for the Price of Anarchy, Proceedings of WAOA 2018, Lecture Notes in Computer Science, accepted, 2018
K. Bérczi, A. Bernáth, M. Vizer: Regular graphs are antimagic, Electronic Journal of Combinatorics, 22:3, P3.34, 2015
E. Ackerman, B. Keszegh, M. Vizer: On the size of planarly connected crossing graphs, Proceedings of Graph Drawing '16, Lecture Notes in Computer Science, 9801, in print, 2016
E. Ackerman, B. Keszegh, M. Vizer: Coloring points with respect to squares, Proceeding of SoCG 2016 (32nd International Symposium on Computational Geometry), LIPIcs – Vol. 51, pp. 5:1-5:16, 2016
S. Aparna Lakshmanan, Cs. Bujtás, Zs. Tuza: Induced cycles in triangle graphs, Discrete Applied Mathematics, 209, 264-275, 2016
Cs. Bujtás, Gy. Dosa, Cs. Imreh, J. Nagy-György, Zs. Tuza: New models of Graph-Bin Packing, Theoretical Computer Science, 640:9, 94--103, 2016
Cs. Bujtás, M.A. Henning, Zs. Tuza: Transversal game on hypergraphs and the 3/4-Conjecture on the total domination game, SIAM Journal on Discrete Mathematics, 2016
Cs. Bujtás, M.A. Henning, and Zs. Tuza: Bounds on the game transversal number in hypergraphs, European Journal of Combinatorics, 59, 34-50, 2017
G. Dosa, Zs. Tuza: Multirofesor Scheduling, Discrete Applied Mathematics, in press, 2016
G. Dosa, H. Kellerer, Zs. Tuza: Team Work Scheduling, MATCOS 16, Middle-European Conference on Applied Theoretical Computer Science, accepted, 2016
D. Gerbner, M. Vizer: A note on tilted Sperner families, Discrete Mathematics, accepted, 2016
Á. Backhausz, B. Gerencsér, V. Harangi, M. Vizer: Correlation bound for distant parts of factor of IID processes, submitted manuscript, 2016
Cs. Bujtás, B. Patkós, Zs. Tuza, M. Vizer: The minimum number of vertices in uniform hypergraphs with given domination number, submitted manuscript, 2016
B. Bresar, Cs. Bujtás, T. Gologranc, S. Klavzar, G. Kosmrlj, B. Patkós, Zs. Tuza, M. Vizer: Dominating sequences in grid-like and toroidal graphs, submitted manuscript, 2016
G. Dosa, H. Kellerer, Zs. Tuza: Restricted assignment scheduling with resource constraints, submitted manuscript, 2016
D. Gerbner, B. Keszegh, G. Mészáros, B. Patkós, M. Vizer: Line percolation in finite projective planes, submitted manuscript, 2016
D. Gerbner, B. Keszegh, D. Pálvölgyi, B. Patkós, M. Vizer, G. Wiener: Finding a majority ball with majority answers, submitted manuscript, 2016
K. Bérczi, A. Bernáth, M. Vizer: Regular graphs are antimagic, Electronic Journal of Combinatorics, 22:3, P3.34, 2015
E. Ackerman, B. Keszegh, M. Vizer: On the size of planarly connected crossing graphs, Journal of Graph Algorithms and Applications (accepted), 2017
E. Ackerman, B. Keszegh, M. Vizer: Coloring points with respect to squares, Discrete and Computational Geometry (accepted), 2017
Cs. Bujtás, Gy. Dosa, Cs. Imreh, J. Nagy-György, Zs. Tuza: New models of Graph-Bin Packing, Theoretical Computer Science, 640:9, 94-103, 2016
Cs. Bujtás, M.A. Henning, Zs. Tuza: Transversal game on hypergraphs and the 3/4-Conjecture on the total domination game, SIAM Journal on Discrete Mathematics, 30:3, 1830-1847, 2016
G. Dosa, Zs. Tuza: Multirofesor Scheduling, Discrete Applied Mathematics, in press, 2017
G. Dosa, H. Kellerer, Zs. Tuza: Team Work Scheduling, Middle-European Conference on Applied Theoretical Computer Science MATCOS 16, 12-13 October 2016, Proceedings of the 19th International Multiconference INFORMATION SOCIET, 2016
D. Gerbner, M. Vizer: A note on tilted Sperner families with patterns, Discrete Mathematics, 339:11, 2737-2741, 2016
Á. Backhausz, B. Gerencsér, V. Harangi, M. Vizer: Correlation bound for distant parts of factor of IID processes, Combinatorics, Probabilty and Computing (accepted), 2016
Cs. Bujtás, B. Patkós, Zs. Tuza, M. Vizer: The minimum number of vertices in uniform hypergraphs with given domination number, Discrete Mathematics, 340:11, 2704-2713, 2017
B. Bresar, Cs. Bujtás, T. Gologranc, S. Klavzar, G. Kosmrlj, B. Patkós, Zs. Tuza, M. Vizer: Dominating sequences in grid-like and toroidal graphs, Electronic Journal of Combinatorics, 23:4, #P4.34, 19 pp., 2016
Cs. Bujtás, Sz. Jaskó: Bounds on the 2-domination number, Discrete Applied Mathematics, in press, 2017
Cs. Bujtás, M. Jakovac: Relating the total domination number and the annihilation number of cactus and block graphs, submitted manuscript, 2017
Cs. Bujtás: On the game total domination number, submitted manuscript, 2017
Cs. Bujtás, Zs. Tuza: F-WORM colorings: Results for 2-connected graphs, Discrete Applied mathematics, 231, 131-138, 2017
Z. Wang, X. Han, Gy. Dósa, Zs. Tuza: A general bin packing game: Interest taken into account, Algorithmica, in press, 2017
Gy. Dósa, A. Fügenschuh, Z. Tan, Zs. Tuza, K. Węsek: Tight upper bounds for semi-online scheduling on two uniform machines with known optimum, Central European Journal of Operations Research, in press, 2017
J. Balogh, J. Bekesi, Gy. Dosa, L. Epstein, A. Levin: Lower bounds for several online variants of bin packing, 15th Workshop on Approximation and Online Algorithms (WAOA 2017), 7-8 September 2017. Vienna, Austria (WAOA), accepted, 2017
J. Balogh, J. Bekesi, Gy. Dosa, L. Epstein, A. Levin: A new and improved algorithm for online bin packing, submitted manuscript, 2017
J. Balogh, J. Bekesi, Gy. Dosa, L. Epstein, A. Levin: Online bin packing with cardinality constraints resolved, ESA 2017 – The 25th Annual European Symposium on Algorithms (ALGO 2017 September 4-8, Vienna, Austria), accepted, 2017
Gy. Dosa, L. Epstein: The convergence time for selfish bin packing, submitted manuscript, 2017
Gy. Dosa, L. Epstein: Selfish bin packing with general weights, submitted manuscript, 2017
Gy. Dosa, L. Epstein: Quality of strong equilibria for selfish bin packing with uniform cost sharing, submitted manuscript, 2017
Gy. Dosa, L. Epstein: The price of anarchy for selfish bin packing with uniform cost sharing, submitted manuscript, 2017
Gy. Dosa, L. Epstein: Pareto optimal equilibria for selfish bin packing with uniform cost sharing, submitted manuscript, 2017
D. Gerbner, B. Patkós, M. Vizer: Forbidden subposet problems for traces of set families, submitted manuscript, 2017
D. Gerbner, B. Keszegh, B. Patkos: Generalized forbidden subposet problems, submitted manuscript, 2017
D. Gerbner, B. Keszegh, C. Palmer, B. Patkós: On the number of cycles in a graph with restricted cycle lengths, SIAM Journal on Discrete Mathematics (accepted), 2017
B. Brešar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, B. Patkós, Zs. Tuza, M. Vizer: Grundy dominating sequences and zero forcing sets, Discrete optimization, in press, 2017
M. Rahman, B. Virág, M. Vizer: Geometry of permutation limits, submitted manuscript, 2017
D. Gerbner, M. Vizer: Majority problems of large query size, submitted manuscript, 2017
D. Gerbner, M. Vizer: Rounds in a combinatorial search problem, submitted manuscript, 2017
D. Gerbner, M.Vizer: Conscious and controlling elements in combinatorial group testing problems, submitted manuscript, 2017
D. Gerbner, A. Methuku, M. Vizer: Asymptotics for the Turán number of Berge-K_{2,t}, submitted manuscript, 2017
D. Gerbner, M. Vizer: Conscious and controlling elements in combinatorial group testing problems with more defectives, submitted manuscript, 2017
D. Gerbner, D. Lenger, M. Vizer: A plurality problem with three colors and query size three, submitted manuscript, 2017
E. Ackerman, B. Keszegh, M. Vizer: On the size of planarly connected crossing graphs, Journal of Graph Algorithms and Applications, 22:1, 11-22, 2018
E. Ackerman, B. Keszegh, M. Vizer: Coloring points with respect to squares, Discrete & Computational Geometry, 58:4, 757-784, 2017
G. Dosa, Zs. Tuza: Multirofesor Scheduling, Discrete Applied Mathematics, 234, 195-209, 2018
G. Dosa, H. Kellerer, Zs. Tuza: Team Work Scheduling, Middle-European Conference on Applied Theoretical Computer Science MATCOS 16, 12-13 October 2016, Proc. 19th International Multiconference INFORMATION SOCIETY, pp. 80-82, 2016
Á. Backhausz, B. Gerencsér, V. Harangi, M. Vizer: Correlation bound for distant parts of factor of IID processes, Combinatorics, Probabilty and Computing, 27:1, 1-20, 2018
G. Dosa, H. Kellerer, Zs. Tuza: Restricted assignment scheduling with resource constraints, Theoretical Computer Science, in print, https://doi.org/10.1016/j.tcs.2018.08.016, 2017
D. Gerbner, B. Keszegh, G. Mészáros, B. Patkós, M. Vizer: Line percolation in finite projective planes, SIAM Journal on Discrete Mathematics, 32:2, 864-881, 2018
D. Gerbner, B. Keszegh, D. Pálvölgyi, B. Patkós, M. Vizer, G. Wiener: Finding a non-minority ball with majority answers, Discrete Applied Mathematics, 219:11, 18-31, 2017
Cs. Bujtás, Sz. Jaskó: Bounds on the 2-domination number, Discrete Applied Mathematics, 242, 4-15, 2018
Cs. Bujtás: On the game total domination number, Graphs and Combinatorics, 34:3, 415-425, 2018
Z. Wang, X. Han, Gy. Dósa, Zs. Tuza: A general bin packing game: Interest taken into account, Algorithmica, 80:5, 1534–1555, 2018
Gy. Dósa, A. Fügenschuh, Z. Tan, Zs. Tuza, K. Węsek: Tight upper bounds for semi-online scheduling on two uniform machines with known optimum, Central European Journal of Operations Research, 26:1, 161–180, 2018
J. Balogh, J. Bekesi, Gy. Dosa, L. Epstein, A. Levin: Lower bounds for several online variants of bin packing, 15th Workshop on Approximation and Online Algorithms (WAOA 2017), 7-8 September 2017. Vienna, Austria (WAOA), Lecture Notes in Computer Science, 10787, 102-117, 2017
J. Balogh, J. Bekesi, Gy. Dosa, L. Epstein, A. Levin: Online bin packing with cardinality constraints resolved, submitted manuscript, 2017
Gy. Dosa, L. Epstein: The convergence time for selfish bin packing, Acta Cybernetica, 23, 853–865, 2018
Gy. Dosa, L. Epstein: Pareto optimal equilibria for selfish bin packing with uniform cost sharing, Journal of Combinatorial Optimization, in print, https://doi.org/10.1007/s10878-018-0323-5, 2018
D. Gerbner, B. Keszegh, C. Palmer, B. Patkós: On the number of cycles in a graph with restricted cycle lengths, SIAM Journal on Discrete Mathematics, 32:1, 266-279, 2018
B. Brešar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, B. Patkós, Zs. Tuza, M. Vizer: Grundy dominating sequences and zero forcing sets, Discrete optimization, 26, 66-77, 2017
M. Rahman, B. Virág, M. Vizer: Geometry of permutation limits, Combinatorica, accepted, 2017
D. Gerbner, M. Vizer: Majority problems of large query size, Discrete Applied Mathematics, in print, https://www.sciencedirect.com/science/article/pii/S0166218X18303512, 2018
D. Gerbner, A. Methuku, M. Vizer: Asymptotics for the Turán number of Berge-K_{2,t}, Journal of Combinatorial Theor Ser. B, accepted, 2017
D. Gerbner, M. Vizer: Smart elements in combinatorial group testing problems, Journal of Combinatorial Optimization, 35:4, 1042-1060, 2018




Back »