Optimal strategies in fractional games: vertex cover and domination

Bujtás, Csilla (author), Rote, Günter (author), Tuza, Zsolt (author)

In a hypergraph ${\cal H}=(V,{\cal E})$ with vertex set $V$ and edge set ${\cal E}$, a real-valued function $f: V \to [0, 1]$ is a fractional transversal if $\sum_{v\in E} f(v) \ge 1$ for every edge $E \in {\cal E}$. Its size is $|f| := \sum_{v \in V} f(v)$, and the fractional transversal number $\tau^\ast({\cal H})$ is the smallest possible $|f|$. We consider a game scenario where two players have opposite goals, one of them trying to minimize and the other to maximize the size of a fractional transversal constructed incrementally. We prove that both players have strategies to achieve their common optimum, and they can reach their goals using rational weights.

• Language: English
• Keywords: fractional vertex cover, fractional transversal game, fractional domination game
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.01.2024
• Year: 2024
• Number of pages: 19 str.
• Numbering: Vol. 24, no. 3, article no. P3.05
• PID: 20.500.12556/RUL-166787
• UDC: 519.17
• ISSN on article: 1855-3966
• DOI: 10.26493/1855-3974.2771.4df
• COBISS.SI-ID: 202315011
• Publication date in RUL: 24.01.2025

Record is a part of a journal

• Title: Ars mathematica contemporanea
• Publisher: Društvo matematikov, fizikov in astronomov, Društvo matematikov, fizikov in astronomov, Univerza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologije
• ISSN: 1855-3966
• COBISS.SI-ID: 239049984

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.