A BRANCH AND BOUND ALGORITHM FOR FINDING THE POSITIVE INFLUENCE DOMINATING SET ON CHORDAL GRAPHS

isolate pendant domination number in semi-total point graphs and its application

Let G be a non-trivial graph. A dominating set I ⊂ V (G) is called an Isolate Pendant Dominating set (IPD-set) if the induced subgraph 〈I〉 has maximum degree at most one and contains at least one isolate vertex and at least one pendant vertex. The minimum cardinality of an IPD-set is called the IP domination number and is denoted by γ01(G). In this paper, we study the IP domination numberbfor semi-total point graphs. We determine exact values of γ_{01}(T_2(G)) for several well-known graph classes, including paths, cycles, and complete graphs. Furthermore, we provide a characterization of IPD-sets in the join of two graphs and examine the behavior of γ01 under the join operation for both arbitrary graphs and semi-total point graphs. Finally, we obtain lower and upper bounds for γ_{01}(T_2(G)) in terms of the order and size of G. The practical relevance of the proposed concepts is illustrated through an application in pest control management.

Upper Clique Transversal on Interval Graphs and Beyond

A 9/4-Approximation for Directed Feedback Vertex Sets in Quasi-Transitive Digraphs

Instance-Optimality of Bidirectional Dijkstra on Simple Graphs

It is shown that bidirectional Dijkstra is still instance-optimal on simple undirected weighted graphs under the order-oblivious model, where incident edges are given in a random order, and under the order-dependent model, where bidirectional Dijkstra is not instance-optimal.

Solving Stackelberg Vertex Cover on trees using split and join

The Stackelberg Vertex Cover problem is a bilevel optimization problem with two players on a graph $G = (F \cup P, E)$ where each vertex from $F$ has a weight and the first player selects a price for each vertex in $P$. Afterwards, the second player finds a minimum vertex cover $X$ and the first player receives the set price for each vertex from $X \cap P$. The goal is to maximize the revenue of the first player. This problem was recently shown to be NP-complete for bipartite graphs while being solvable in linear time on paths. We present three new algorithms for solving Stackelberg Vertex Cover on certain kinds of trees: (1) a pseudo-polynomial algorithm working on general trees when all weights are integer, i.e., it is FPT with the maximum weight as a parameter; (2) a strongly polynomial algorithm for trees having the property that the least common ancestor of any two vertices from $P$ is again in $P$ (this case includes paths); and (3) an FPT-algorithm for trees, where the parameter is the maximum number $P$-vertices $v_i$ that an $F$-vertex $u$ can reach while using no other $P$-vertices. These algorithms are based on a lemma that allows us to split instances at a vertex $u$ into multiple sub-instances, which follows from LP duality and integrality of the vertex cover LP on bipartite graphs. The lemma requires that the minimum vertex covers of the sub-instances agree on $u$ (either all include $u$ or all don't). For this we introduce the concept of commitments. Finally, we show that the Stackelberg Vertex Cover problem with commitments is weakly NP-complete.

Spread of influence in weighted networks under time and budget constraints ✩

It is proved that the problem of defining a bounded cost set of nodes S such that the influence spreading from S in G, within a given time bound, is as large as possible, and that the problem is NP-hard, even in simple networks like complete graphs and trees.