We show that for a fixed $r$, the number of maximal $r$-regular induced subgraphs in any graph with $n$ vertices is upper bounded by $\mathcal{O}(c^n)$, where $c$ positive constant strictly less than $2$. This bound generalizes well-known result Moon and Moser, who showed an $3^{n/3}$ on independent sets vertices. complement this obtaining almost tight lower (possible) possible Our results are algorithmic. That is, we can enumerate all time $\mathcal{O}(c^n n^{\mathcal{O}(1)})$. A related...

An input to the P OPULAR M ATCHING problem, in roommates setting (as opposed marriage setting), consists of a graph G (not necessarily bipartite) where each vertex ranks its neighbors strict order, known as preference. In problem objective is test whether there exists matching * such that no more vertices prefer their matched status (in terms preferences) over *. this article, we settle computational complexity by showing NP-complete. Thus, resolve an open question has been repeatedly and...

Allocating conflicting jobs among individuals while respecting a budget constraint for each individual is an optimization problem that arises in various real-world scenarios. In this paper, we consider the situation where derives some satisfaction from job. We focus on finding feasible allocation of maximize egalitarian cost, i.e., who worst-off. To best our knowledge, first paper to combine egalitarianism, budget-feasibility, and conflict-freeness allocations. provide systematic study...

In this paper we study the independent version of classic Feedback Vertex Set problem in realm parameterized algorithms and moderately exponential time algorithms. More precisely, Independent problem, where are given an undirected graph G on n vertices a positive integer k, objective is to check if there feedback vertex set size at most k. A S subseteq V(G) called (ifvs) G\S forest. design two deterministic exact for with running times O*(4.1481^k) O*(1.5981^n). fact, algorithm O*(1.5981^n)...

An input to the Popular Matching problem, in roommates setting, consists of a graph G where each vertex ranks its neighbors strict order, known as preference. In problem objective is test whether there exists matching M* such that no M more people (vertices) are happier (in terms preferences) with than M*. this paper we settle computational complexity setting by showing NP-complete. Thus, resolve an open question has been repeatedly and explicitly asked over last decade.

A knockout tournament is a standard format of competition, ubiquitous in sports, elections and decision making. Such competition consists several rounds. In each round, all players that have not yet been eliminated are paired up into matches. Losers eliminated, winners raised to the next until only one winner exists. Given we can correctly predict outcome potential match (modelled by D), seeding deterministically determines its winner. Having favorite player v mind, Tournament Fixing Problem...

In a tournament, $n$ players enter the competition. each round, they are paired-up to compete against other. Losers thrown, while winners proceed next until only one player (the winner) is left. Given prediction of outcome, for every pair players, match between them (modeled by digraph $D$), competitive nature tournament makes it attractive manipulators. Tournament Fixing (TF) problem, goal decide if we can conduct competition (by controlling how paired-up) so that our favorite $w$ wins. A...

Single-elimination (SE) tournaments are a popular format used in competitive environments and decision making. Algorithms for SE tournament manipulation have been an active topic of research recent years. In this paper, we initiate the algorithmic study novel variant that aims to model fact certain matchups highly desired sporting context, incentivizing organizer manipulate bracket make such take place. We obtain both hardness tractability results. show while problem computing enforcing...

Single-elimination tournaments are a popular format in competitive environments. The Tournament Fixing Problem (TFP), which is the problem of finding seeding players such that certain player wins resulting tournament, known to be NP-hard general and fixed-parameter tractable when parameterized by feedback arc set number input tournament (an oriented complete graph) expected wins/loses. However, existence polynomial kernelizations (efficient preprocessing) for TFP has remained open. In this...