Search

We introduce the rendezvous game with adversaries. In this game, two players, Facilitator and Divider , play against each other on a graph. Facilitator has two agents and Divider has a team of k agents located in some vertices. They take turns in moving their agents to adjacent vertices (or staying put). Facilitator wins if his agents meet in some vertex. Divider aims to prevent the rendezvous of Facilitator's agents. We show that deciding whether Facilitator can win is PSPACE -hard and, when parameterized by k , co-W [ 2 ] -hard. Moreover, even deciding whether Facilitator can win within τ steps is co-NP -complete already for τ = 2. On the other hand, for chordal and P 5 -free graphs, we prove that the problem is solvable in polynomial time. Finally, we show that the problem is fixed-parameter tractable parameterized by both the graph's neighborhood diversity and the number of steps τ. [ABSTRACT FROM AUTHOR]

We consider the Edge Editing to a Connected Graph of Given Degrees problem that asks, given a graph G , non-negative integers d , k and a function δ : V ( G ) → { 1 , … , d } , whether it is possible to obtain a connected graph G ′ from G such that the degree of v is δ ( v ) for every vertex v by at most k edge editing operations. As the problem is NP-complete even if δ ( v ) = 2 , we are interested in the parameterized complexity and show that Edge Editing to a Connected Graph of Given Degrees admits a polynomial kernel when parameterized by d + k . For the special case δ ( v ) = d , i.e., when the aim is to obtain a connected d -regular graph, the problem is shown to be fixed parameter tractable when parameterized by k only. [ABSTRACT FROM AUTHOR]

If a graph G contains no subgraph isomorphic to some graph H, then G is called H-free. A coloring of a graph G=(V,E) is a mapping c:V→{1,2,...} such that no two adjacent vertices have the same color, i.e., c(u)≠c(v) if uv∈E; if |c(V)|≼k then c is a k-coloring. The Coloring problem is to test whether a graph has a coloring with at most k colors for some integer k. The Precoloring Extension problem is to decide whether a partial k-coloring of a graph can be extended to a k-coloring of the whole graph for some integer k. The List Coloring problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L(u). By imposing an upper bound ł on the size of each L(u) we obtain the ł-List Coloring problem. We first classify the Precoloring Extension problem and the ł-List Coloring problem for H-free graphs. We then show that 3-List Coloring is NP-complete for n-vertex graphs of minimum degree n-2, i.e., for complete graphs minus a matching, whereas List Coloring is fixed-parameter tractable for this graph class when parameterized by the number of vertices of degree n-2. Finally, for a fixed integer k>0, the Listk-Coloring problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L(u) that must be a subset of {1,...,k}. We show that List 4-Coloring is NP-complete for P6-free graphs, where P6 is the path on six vertices. This completes the classification of Listk-Coloring for P6-free graphs. [ABSTRACT FROM AUTHOR]

We consider the Directed Anchored k -Core problem, where the task is for a given directed graph G and integers b , k and p , to find an induced subgraph H with at least p vertices (the core) such that all but at most b vertices (the anchors) of H have in-degree at least k . We undertake a systematic analysis of the computational complexity of the Directed Anchored k -Core problem. [ABSTRACT FROM AUTHOR]