We present new results on Maker-Breaker games arising from the Erdős-Szekeres problem in planar geometry. This classical problem asks how large a set in general position has to be to ensure the existence of n points that are the vertices of a convex n-gon. Moreover, Erdős further extended this problem by asking what happens if we also require that this n-gon has an empty interior. In a 2-player Maker-Breaker setting, this problem inspires two main games. In both games, Maker tries to obtain an empty convex k-gon, while Breaker tries to prevent her from doing so. The games differ only in which points can comprise the winning k-gons: in the monochromatic version the points of both players can make up a k-gon, while in the bichromatic version only Maker’s points contribute to such a polygon. Both settings are studied in this paper. We show that in the monochromatic game, Maker always wins. Even in a biased game where Breaker is allowed to place s points per round, for any constant $$s \ge 1$$ , Maker has a winning strategy. In the bichromatic setting, Maker still wins whenever Breaker is allowed to place s points per round for any constant $$s<2$$ . This settles an open problem posed in 2019. Furthermore, we show that there are games that are not a lost cause for Breaker. Whenever $$k\ge 8$$ and Breaker is allowed to play 12 or more points per round, she has a winning strategy. We also consider the one-round bichromatic game (a.k.a. the offline version). In this setting, we show that Breaker wins if she can place twice as many points as Maker but if the bias is less than 2, then Maker wins for large enough set of points.

We study the heterogeneous facility location game model of n selfish agents on a line, where each agent’s reachable range is a closed subinterval of the line. From two possible facilities, f1 and f2, exactly one is chosen to be built on some point of the line, and the agents have their own preferences p1, p2∈[0,1], p1+p2=1, over these two facilities. The utility of the agent is pi if the placement of the chosen facility fi is inside her reachable range, and zero otherwise. The task is to design mechanisms which get the input from the agents and select the type and placement point of the facility to be built, such that it maximizes the social welfare (defined as the total utility of all agents) while ensuring truthfulness, i.e., incentivizing agents to report their preferences (both facility type and placement) honestly as a dominant strategy. We analyze various scenarios with different setting of privacy of agents’ positional and preference information. When the information is private to the agent, they have the option to misreport it, and hence, we will distinguish between reported information and public information. Initially, we consider the case where all facility preferences are 0 or 1 and we design an optimal mechanism for this case. We then study the case with fractional facility preferences. For the case of public preferences and reported positions, we obtain a mechanism yielding a 3-approximation of the optimum social welfare, and we prove that no deterministic mechanism can achieve approximation ratio better than 4/3. Next, we study the case with public positions and reported preferences. In this setting we design a randomized 2-approximation, obtain lower bounds 3 and 3/2 for the approximation factor of deterministic and randomized strategyproof mechanisms, respectively, and show that a dictator-based approach is a 16/7-approximation mechanism, where the 16/7 factor is tight. Finally, we extend our results to the case of m facilities.

Let G be a graph with a set of precolored vertices, and let us be given an integer distance parameter d and a set of integer demands d₁,… ,d_c. The Distance Precoloring Extension with Demands (DPED) problem is to compute a vertex c-coloring of G such that the following three conditions hold: (i) the resulting coloring respects the colors of the precolored vertices, (ii) the distance of two vertices of the same color is at least d, and (iii) the number of vertices colored by color i is exactly d_i. This problem is motivated by a program scheduling in commercial broadcast channels with constraints on content repetition and placement, which leads precisely to the DPED problem for paths. In this paper, we study DPED on paths and present a polynomial time exact algorithm when precolored vertices are restricted to the two ends of the path and devise an approximation algorithm for DPED with an additive approximation factor polynomially bounded by d and the number of precolored vertices. Then, we prove that the Distance Precoloring Extension problem on paths, a less restrictive version of DPED without the demand constraints, and then DPED itself, is NP-complete. Motivated by this result, we further study the parameterized complexity of DPED on paths. We establish that the DPED problem on paths is W[1]-hard when parameterized by the number of colors and the distance. On the positive side, we devise a fixed parameter tractable (FPT) algorithm for DPED on paths when the number of colors, the distance, and the number of precolored vertices are considered as the parameters. Moreover, we prove that Distance Precoloring Extension is FPT parameterized by the distance. As a byproduct, we also obtain several results for the Distance List Coloring problem on paths.

For many problems, the important instances from practice possess certain structure that one should reflect in the design of specific algorithms. As data reduction is an important and inextricable part of today's computation, we employ one of the most successful models of such precomputation -- the kernelization. Within this framework, we focus on Traveling Salesperson Problem (TSP) and some of its generalizations. We provide a kernel for TSP with size polynomial in either the feedback edge set number or the size of a modulator to constant-sized components. For its generalizations, we also consider other structural parameters such as the vertex cover number and the size of a modulator to constant-sized paths. We complement our results from the negative side by showing that the existence of a polynomial-sized kernel with respect to the fractioning number, the combined parameter maximum degree and treewidth, and, in the case of Subset-TSP, modulator to disjoint cycles (i.e., the treewidth two graphs) is unlikely.

Abstract Consider a vertex-weighted graphGwith a sourcesand a targett.Tracking Pathsrequires finding a minimum weight set of vertices (trackers) such that the sequence of trackers in each path fromstotis unique. In this work, we derive a factor 66-approximation algorithm forTracking Pathsin weighted graphs and a factor 4-approximation algorithm if the input is unweighted. This is the first constant factor approximation for this problem. While doing so, we also study approximation of the closely relatedr-Fault Tolerant Feedback Vertex Setproblem. There, for a fixed integer rand a given vertex-weighted graphG, the task is to find a minimum weight set of vertices intersecting every cycle of Gin at least $$r+1$$ r+1 vertices. We give a factor $$\mathcal {O}(r^2)$$ O(r2) approximation algorithm forr-Fault Tolerant Feedback Vertex Setifris a constant.

Let G be a graph and let $c: V(G)\to\binom{1,\ldots,5}{2}$ be an assignment of 2-element subsets of the set $1,\ldots,5$ to the vertices of G such that for every edge $vw$, the sets $c(v)$ and $c(w)$ are disjoint. We call such an assignment a $(5,2)$-coloring. A graph is (5,2)-colorable if and only if it has a homomorphism to the Petersen graph. The odd-girth of a graph G is the length of the shortest odd cycle in G ($\infty$ if G is bipartite). We prove that every planar graph of odd-girth at least 9 is $(5,2)$-colorable, and thus it is homomorphic to the Petersen graph. Also, this implies that such graphs have a fractional chromatic number at most $5\over2$. As a special case, this result holds for planar graphs of girth at least 8.