Search

Property testing is a rapid growing field in theoretical computer science. It considers the following task: given a function f over a domain D, a property ℘ and a parameter 0< ε<1, by examining function values of f over o(| D|) elements in D, determine whether f satisfies ℘ or differs from any one which satisfies ℘ in at least ε| D| elements. An algorithm that fulfills this task is called a property tester. We focus on tree-likeness of quartet topologies, which is a combinatorial property originating from evolutionary tree construction. The input function is f, which assigns one of the three possible topologies for every quartet over an n-taxon set S. We say that f satisfies tree-likeness if there exists an evolutionary tree T whose induced quartet topologies coincide with f. In this paper, we prove the existence of a set of quartet topologies of error number at least $c{n\choose 4}$ for some constant c>0, and present the first property tester for tree-likeness of quartet topologies. Our property tester makes at most O( n/ ε) queries, and is of one-sided error and non-adaptive. [ABSTRACT FROM AUTHOR]

Let S be a set of n taxa. Given a parameter k and a set of quartet topologies Q over S such that there is exactly one topology for every subset of four taxa, the parameterized Minimum Quartet Inconsistency (MQI) problem is to decide whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given set in at most k quartet topologies. The best fixed-parameter algorithm devised so far for the parameterized MQI problem runs in time O(4 k n+ n4). In this paper, first we present an O(3.0446 k n+ n4) fixed-parameter algorithm and an O(2.0162 k n3+ n5) fixed-parameter algorithm for the parameterized MQI problem. Finally, we give an O*((1+ ε) k) fixed-parameter algorithm, where ε>0 is an arbitrarily small constant. [ABSTRACT FROM AUTHOR]

From a perspective of designing or engineering for opinion formation games in social networks, the opinion maximization (or minimization) problem has been studied mainly for designing seeding algorithms that aim at selecting a subset of nodes to control their opinions. We first define a two-player zero-sum Stackelberg game of competitive opinion optimization by letting the player under study as the leader minimize the sum of expressed opinions by doing so-called "internal opinion design", knowing that the other adversarial player as the follower is to maximize the same objective by also conducting her own internal opinion design. We furthermore consider multiagent learning, specifically using the Optimistic Gradient Descent Ascent, and analyze its convergence to equilibria in the simultaneous-game version of competitive opinion optimization. [ABSTRACT FROM AUTHOR]