BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Kaveh Khoshkhah appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We bound the number of minimal hypergraph transversals that arise in tri-partite 3-uniform hypergraphs, a class commonly found in applications dealing with data. Let H be such a hypergraph on a set of vertices V. We give a lower bound of 1.4977 |V | and an upper bound of 1.5012 |V | .
In the study of extensions of polytopes of combinatorial optimization problems, a notorious open question is that for the size of the smallest extended formulation of the Minimum Spanning Tree problem on a complete graph with $n$ nodes. The best known lower bound is $Ω(n^2)$, the best known upper bound is $O(n^3)$. In this note we show that the venerable fooling set method cannot be used to improve the lower bound: every fooling set for the Spanning Tree polytope has size $O(n^2)$.
Given an undirected graph, each of the two end-vertices of an edge can own the edge. Call a vertex poor, if it owns at most one edge. We give a polynomial time algorithm for the problem of finding an assignment of owners to the edges which minimizes the number of poor vertices. In the terminology of graph orientation, this means finding an orientation for the edges of a graph minimizing the number of edges with out-degree at most 1, and answers a question of Asahiro Jansson, Miyano, Ono (2014).
Let $G$ be a graph and $τ$ be an assignment of nonnegative integer thresholds to the vertices of $G$. A subset of vertices $D$ is said to be a $τ$-dynamic monopoly, if $V(G)$ can be partitioned into subsets $D_0, D_1, \ldots, D_k$ such that $D_0=D$ and for any $i\in \{0, \ldots, k-1\}$, each vertex $v$ in $D_{i+1}$ has at least $τ(v)$ neighbors in $D_0\cup \ldots \cup D_i$. Denote the size of smallest $τ$-dynamic monopoly by $dyn_τ(G)$ and the average of thresholds in $τ$ by $\overlineτ$. We show that the values of $dyn_τ(G)$ over all assignments $τ$ with the same average threshold is a continuous set of integers. For any positive number $t$, denote the maximum $dyn_τ(G)$ taken over all threshold assignments $τ$ with $\overlineτ\leq t$, by $Ldyn_t(G)$. In fact, $Ldyn_t(G)$ shows the worst-case value of a dynamic monopoly when the average threshold is a given number $t$. We investigate under what conditions on $t$, there exists an upper bound for $Ldyn_{t}(G)$ of the form $c|G|$, where $c<1$. Next, we show that $Ldyn_t(G)$ is coNP-hard for planar graphs but has polynomial-time solution for forests.
Let $G$ be a directed graph such that the in-degree of any vertex $G$ is at least one. Let also ${\mathcalτ}: V(G)\rightarrow \Bbb{N}$ be an assignment of thresholds to the vertices of $G$. A subset $M$ of vertices of $G$ is called a dynamic monopoly for $(G,τ)$ if the vertex set of $G$ can be partitioned into $D_0\cup... \cup D_t$ such that $D_0=M$ and for any $i\geq 1$ and any $v\in D_i$, the number of edges from $D_0\cup... \cup D_{i-1}$ to $v$ is at least $τ(v)$. One of the most applicable and widely studied threshold assignments in directed graphs is strict majority threshold assignment in which for any vertex $v$, $τ(v)=\lceil (deg^{in}(v)+1)/2 \rceil$, where $deg^{in}(v)$ stands for the in-degree of $v$. By a strict majority dynamic monopoly of a graph $G$ we mean any dynamic monopoly of $G$ with strict majority threshold assignment for the vertices of $G$. In this paper we first discuss some basic upper and lower bounds for the size of dynamic monopolies with general threshold assignments and then obtain some hardness complexity results concerning the smallest size of dynamic monopolies in directed graphs. Next we show that any directed graph on $n$ vertices and with positive minimum in-degree admits a strict majority dynamic monopoly with $n/2$ vertices. We show that this bound is achieved by a polynomial time algorithm. This upper bound improves greatly the best known result. The final note of the paper deals with the possibility of the improvement of the latter $n/2$ bound.
Let $G$ be a graph and ${\mathcalτ}: V(G)\rightarrow \Bbb{N}\cup \{0\}$ be an assignment of thresholds to the vertices of $G$. A subset of vertices $D$ is said to be a dynamic monopoly corresponding to $(G, τ)$ if the vertices of $G$ can be partitioned into subsets $D_0, D_1,..., D_k$ such that $D_0=D$ and for any $i\in {0, ..., k-1}$, each vertex $v$ in $D_{i+1}$ has at least $τ(v)$ neighbors in $D_0\cup ... \cup D_i$. Dynamic monopolies are in fact modeling the irreversible spread of influence in social networks. In this paper we first obtain a lower bound for the smallest size of any dynamic monopoly in terms of the average threshold and the order of graph. Also we obtain an upper bound in terms of the minimum vertex cover of graphs. Then we derive the upper bound $|G|/2$ for the smallest size of any dynamic monopoly when the graph $G$ contains at least one odd vertex, where the threshold of any vertex $v$ is set as $\lceil (deg(v)+1)/2 \rceil$ (i.e. strict majority threshold). This bound improves the best known bound for strict majority threshold. We show that the latter bound can be achieved by a polynomial time algorithm. We also show that $α'(G)+1$ is an upper bound for the size of strict majority dynamic monopoly, where $α'(G)$ stands for the matching number of $G$. Finally, we obtain a basic upper bound for the smallest size of any dynamic monopoly, in terms of the average threshold and vertex degrees. Using this bound we derive some other upper bounds.