Arrow Research search

Author name cluster

Anders Yeo

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

12 papers
2 author rows

Possible papers

12

AAAI Conference 2026 Conference Paper

Public Goods Games in Directed Networks with Constraints on Sharing

  • Argyrios Deligkas
  • Gregory Gutin
  • Mark Jones
  • Philip R. Neary
  • Anders Yeo

In a public goods game, every player chooses whether or not to buy a good that all neighboring players will have access to. We consider a setting in which the good is indivisible, neighboring players are out-neighbors in a directed graph, and there is a capacity constraint on their number, k, that can benefit from the good. This means that each player makes a two-pronged decision: decide whether or not to buy and, conditional on buying, choose which k out-neighbors to share access. We examine both pure and mixed Nash equilibria in the model from the perspective of existence, computation, and efficiency. We perform a comprehensive study for these three dimensions with respect to both sharing capacity (k) and the network structure (the underlying directed graph), and establish sharp complexity dichotomies for each.

PDF Details DOI

IJCAI Conference 2023 Conference Paper

Complexity of Efficient Outcomes in Binary-Action Polymatrix Games and Implications for Coordination Problems

  • Argyrios Deligkas
  • Eduard Eiben
  • Gregory Gutin
  • Philip Neary
  • Anders Yeo

We investigate the difficulty of finding economically efficient solutions to coordination problems on graphs. Our work focuses on two forms of coordination problem: pure-coordination games and anti-coordination games. We consider three objectives in the context of simple binary-action polymatrix games: (i) maximizing welfare, (ii) maximizing potential, and (iii) finding a welfare-maximizing Nash equilibrium. We introduce an intermediate, new graph-partition problem, termed MWDP, which is of independent interest, and we provide a complexity dichotomy for it. This dichotomy, among other results, provides as a corollary a dichotomy for Objective (i) for general binary-action polymatrix games. In addition, it reveals that the complexity of achieving these objectives varies depending on the form of the coordination problem. Specifically, Objectives (i) and (ii) can be efficiently solved in pure-coordination games, but are NP-hard in anti-coordination games. Finally, we show that objective (iii) is NP-hard even for simple non-trivial pure-coordination games.

PDF Details DOI

MFCS Conference 2021 Conference Paper

Perfect Forests in Graphs and Their Extensions

  • Gregory Z. Gutin
  • Anders Yeo

Let G be a graph on n vertices. For i ∈ {0, 1} and a connected graph G, a spanning forest F of G is called an i-perfect forest if every tree in F is an induced subgraph of G and exactly i vertices of F have even degree (including zero). An i-perfect forest of G is proper if it has no vertices of degree zero. Scott (2001) showed that every connected graph with even number of vertices contains a (proper) 0-perfect forest. We prove that one can find a 0-perfect forest with minimum number of edges in polynomial time, but it is NP-hard to obtain a 0-perfect forest with maximum number of edges. We also prove that for a prescribed edge e of G, it is NP-hard to obtain a 0-perfect forest containing e, but we can find a 0-perfect forest not containing e in polynomial time. It is easy to see that every graph with odd number of vertices has a 1-perfect forest. It is not the case for proper 1-perfect forests. We give a characterization of when a connected graph has a proper 1-perfect forest.

Details

SAT Conference 2012 Conference Paper

Fixed-Parameter Tractability of Satisfying beyond the Number of Variables

  • Robert Crowston
  • Gregory Z. Gutin
  • Mark Jones 0001
  • Venkatesh Raman 0001
  • Saket Saurabh 0001
  • Anders Yeo

Abstract We consider a CNF formula F as a multiset of clauses: F = { c 1, …, c m }. The set of variables of F will be denoted by V ( F ). Let B F denote the bipartite graph with partite sets V ( F ) and F and an edge between v ∈ V ( F ) and c ∈ F if v ∈ c or \(\bar{v} \in c\). The matching number ν ( F ) of F is the size of a maximum matching in B F. In our main result, we prove that the following parameterization of MaxSat is fixed-parameter tractable: Given a formula F, decide whether we can satisfy at least ν ( F ) + k clauses in F, where k is the parameter. A formula F is called variable-matched if ν ( F ) = | V ( F )|. Let δ ( F ) = | F | − | V ( F )| and δ * ( F ) = max F ′ ⊆ F δ ( F ′). Our main result implies fixed-parameter tractability of MaxSat parameterized by δ ( F ) for variable-matched formulas F; this complements related results of Kullmann (2000) and Szeider (2004) for MaxSat parameterized by δ * ( F ). To prove our main result, we obtain an O ((2 e ) 2 k k O (log k ) ( m + n ) O (1) )-time algorithm for the following parameterization of the Hitting Set problem: given a collection \(\cal C\) of m subsets of a ground set U of n elements, decide whether there is X ⊆ U such that C ∩ X ≠ ∅ for each \(C\in \cal C\) and | X | ≤ m − k, where k is the parameter. This improves an algorithm that follows from a kernelization result of Gutin, Jones and Yeo (2011).

Details

MFCS Conference 2012 Conference Paper

Parameterized Study of the Test Cover Problem

  • Robert Crowston
  • Gregory Z. Gutin
  • Mark Jones 0001
  • Saket Saurabh 0001
  • Anders Yeo

Abstract In this paper we carry out a systematic study of a natural covering problem, used for identification across several areas, in the realm of parameterized complexity. In the Test Cover problem we are given a set [ n ] = {1, …, n } of items together with a collection, \(\cal T\), of distinct subsets of these items called tests. We assume that \(\cal T\) is a test cover, i. e. , for each pair of items there is a test in \(\cal T\) containing exactly one of these items. The objective is to find a minimum size subcollection of \(\cal T\), which is still a test cover. The generic parameterized version of Test Cover is denoted by \(p(k, n, |{\cal T}|)\) - Test Cover. Here, we are given \(([n], \cal{T})\) and a positive integer parameter k as input and the objective is to decide whether there is a test cover of size at most \(p(k, n, |{\cal T}|)\). We study four parameterizations for Test Cover and obtain the following: (a) k - Test Cover, and ( n − k )- Test Cover are fixed-parameter tractable (FPT), i. e. , these problems can be solved by algorithms of runtime \(f(k)\cdot poly(n, |{\cal T}|)\), where f ( k ) is a function of k only. (b) \((|{\cal T}|-k)\) - Test Cover and (log n + k )- Test Cover are W[1]-hard. Thus, it is unlikely that these problems are FPT.

Details