Optimal strategies in fractional games: vertex cover and domination

MaRDI QIDQ6367186zbMATH OpenFDO

Authors Csilla Bujtás, Günter Rote, Zsolt Tuza

Publication date 9 May 2021

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Games on graphs (graph-theoretic aspects) (05C57) Hypergraphs (05C65)

Abstract: In a hypergraph with vertex set $V$ and edge set $E$, a real-valued function $f:Vo[0,1]$ is a fractional transversal if $su{m}_{vine}f(v)ge1$ for every edge $einE$. Its size is $|f|:=su{m}_{vinV}f(v)$, and the fractional transversal number is the smallest possible $|f|$. We consider a game scenario where two players with opposite goals construct a fractional transversal incrementally, trying to minimize and maximize $|f|$, respectively. We prove that both players have strategies to achieve their common optimum, and they can reach their goals using rational weights.

This page was built for publication: Optimal strategies in fractional games: vertex cover and domination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6367186)