Search

We show that the TEMPORAL GRAPH EXPLORATION PROBLEM is NP-complete, even when the underlying graph has pathwidth 2 and at each time step, the current graph is connected. (C) 2018 Elsevier B.V. All rights reserved.

A $k$-subcoloring of a graph is a partition of the vertex set into at most $k$ cluster graphs, that is, graphs with no induced $P_3$. 2-subcoloring is known to be NP-complete for comparability graphs and three subclasses of planar graphs, namely triangle-free planar graphs with maximum degree 4, planar perfect graphs with maximum degree 4, and planar graphs with girth 5. We show that 2-subcoloring is also NP-complete for planar comparability graphs with maximum degree 4.

We show that the Temporal Graph Exploration Problem is NP-complete, even when the underlying graph has pathwidth 2 and at each time step, the current graph is connected.

We show that the Temporal Graph Exploration Problem is NP-complete, even when the underlying graph has pathwidth 2 and at each time step, the current graph is connected.

The identifying code problem is a special search problem, challenging both from a theoretical and from a computational point of view, even for several graphs where other usually hard problems are easy to solve, like bipartite graphs or chordal graphs. Hence, a typical line of attack for this problem is to determine minimum identifying codes of special graphs. In this work we study the problem of determining the cardinality of a minimum identifying code in block graphs (that are diamond-free chordal graphs). We present a linear-time algorithm for this problem, as a generalization of a linear-time algorithm proposed by Auger in 2010 for the case of trees. Thereby, we provide a subclass of chordal graphs for which the identifying code problem can be solved in linear time. Fil: Argiroffo, Gabriela Rut. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina Fil: Bianchi, Silvia María. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina Fil: Lucarini, Yanina Paola. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina Fil: Wagler, Annegret Katrin. University Clermont Auvergne; Francia

International audience; In this paper, we consider the selective graph coloring problem. Given an integer k≥1k≥1 and a graph G=(V,E)G=(V,E) with a partition V1,…,VpV1,…,Vp of VV, it consists in deciding whether there exists a set V∗V∗ in GG such that ∣V∗∩Vi∣=1∣V∗∩Vi∣=1 for all i∈{1,…,p}i∈{1,…,p}, and such that the graph induced by V∗V∗ is kk-colorable. We investigate the complexity status of this problem in various classes of graphs.

In this work we obtain a new graph class where the {. k}-dominating function problem ({. k}-DOM) is NP-complete: the class of chordal graphs. We also identify some maximal subclasses for which it is polynomial time solvable. Firstly, by relating this problem with the k-dominating function problem (k-DOM), we prove that {. k}-DOM is polynomial time solvable for strongly chordal graphs. Besides, by expressing the property involved in k-DOM in Counting Monadic Second-order Logic, we obtain that both problems are linear time solvable for bounded tree-width graphs. Finally, we show that {. k}-DOM is linear time solvable for spider graphs. Fil: Argiroffo, Gabriela Rut. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina Fil: Leoni, Valeria Alejandra. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina Fil: Torres, Pablo Daniel. Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina

In the edge searching problem searchers move from vertex to vertex in a graph to capture an invisible fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which at every move a new edge of the graph G must be guaranteed to be free of the intruder. That is once all searchers are placed the graph G is cleared in exactly vertical bar E(G)vertical bar moves. Such a restriction obviously necessitates a larger number of searchers. We examine this model and characterize graphs for which 2 or 3 searchers are sufficient. We prove that the corresponding decision problem is NP-complete. (C) 2013 Elsevier B.V. All rights reserved.

The dual bandwidth of a graph, is the maximum value of the minimum labeling variance of any two adjacent vertices. The computational complexity of finding the dual bandwidth of a general graph is Np-complete. Even the problem of deciding whether the dual bandwidth of graph is two or not is Np-complete. Therefore, we consider the dual bandwidth of special graphs- the product of two paths. We find the upper and lower bound of these graphs.

The Honey-Bee game is a two-player board game that is played on a connected hexagonal colored grid or (in a generalized setting) on a connected graph with colored nodes. In a single move, a player calls a color and thereby conquers all the nodes of that color that are adjacent to his own current territory. Both players want to conquer the majority of the nodes. We show that winning the game is PSPACE-hard in general, NP-hard on series-parallel graphs, but easy on outerplanar graphs. In the solitaire version, the goal of the single player is to conquer the entire graph with the minimum number of moves. The solitaire version is NP-hard on trees and split graphs, but can be solved in polynomial time on co-comparability graphs., 20 pages, 9 figures

We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the graph. We resolve the square-root conjecture, first posed at MFCS 2004, by showing that for a reducible graph $G$, the minimum number of required rounds is $O(\sqrt{n})$; in fact, our result is stronger than the conjecture as we show that the minimum number of required rounds is $O(\sqrt{\alpha})$, where $\alpha$ is the independence number of $G$. This upper bound is tight. We also show that for reducible $K_{1,p}$-free graphs at most $p-1$ rounds are required. It is already known that the problem of whether a given graph is reducible is NP-complete. For claw-free graphs, however, we show that this problem can be solved in polynomial time. We also pinpoint a relationship with (locally bijective) graph homomorphisms.

We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for a given bipartite graph, such a scheme can be found that eliminates every vertex is NP-complete. Moreover, we show that, for all fixed positive integers $k\ge 2$, the problem of whether a given bipartite graph admits a scheme in which all vertices are eliminated in at most (exactly) $k$ rounds is NP-complete. For graphs with bounded tree-width, however, both of these problems are shown to be solvable in polynomial time. We also show that $r$-regular graphs with $r\ge 1$, factor-critical graphs and 1-tough graphs admit a scheme in which all vertices are eliminated in one round.

The minimum all-ones problem and the connected odd dominating set problem were shown to be NP-complete in different papers for general graphs, while they are solvable in linear time (or trivial) for trees, unicyclic graphs, and series-parallel graphs. The complexity of both problems when restricted to bipartite graphs was raised as an open question. Here we solve both problems. For this purpose, we introduce the related decision problem of the existence of an odd dominating set without isolated vertices, and study its complexity. Our main result shows that this new problem is NP-complete, even when restricted to bipartite graphs. We use this result to deduce that the minimum all-ones problem and the connected odd dominating set problem are also NP-complete for bipartite graphs. We show that all three problems are solvable in linear time for graphs with bounded treewidth. We also show that the new problem remains NP-complete when restricted to other graph classes, e.g., planar graphs, graphs with girth at least five, and graphs with a small maximum degree, in particular 3-regular graphs.

A parallel knock-out scheme for a graph proceeds in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is KO-reducible if there exists such a scheme that eliminates every vertex in the graph. The Parallel Knock-Out problem is to decide whether a graph GG is KO-reducible. This problem is known to be NP-complete and has been studied for several graph classes. We show that the problem is NP-complete even for split graphs, a subclass of P5P5-free graphs. In contrast, our main result is that it is linear-time solvable for P4P4-free graphs (cographs).

Graph Theory, Given a graph and a positive integer k, the biclique vertex-partition problem asks whether the vertex set of the graph can be partitioned into at most k bicliques (connected complete bipartite subgraphs). It is known that this problem is NP-complete for bipartite graphs. In this paper we investigate the computational complexity of this problem in special subclasses of bipartite graphs. We prove that the biclique vertex-partition problem is polynomially solvable for bipartite permutation graphs, bipartite distance-hereditary graphs and remains NP-complete for perfect elimination bipartite graphs and bipartite graphs containing no 4-cycles as induced subgraphs.

We provide two polynomial-time exact algorithms to compute a maximum stable set in graphs that are respectively ( P 6 , triangle)-free, and ( P 6 , C 4 )-free. The algorithm devised for ( P 6 , C 4 )-free graphs is based on the search of simple augmenting trees and can be extended to heuristically solve the problem in a general graph.

We suggest a uniform game-theoretic approach to “width” graph parameters. We consider a search problem on a graph in which one cop in a helicopter flying from vertex to vertex tries to catch the robber. The existence of the winning program for the cop in this problem depends only on the robber's speed. We investigate the problem of finding the minimal robber's speed which prevents the cop from winning. We examine two cases of the problem. In the first one the cop can visit each vertex of a graph only once. In the second case the cop cannot afford “recontamination” of vertices. We show that in the first case the problem of finding the minimal robber's speed is equivalent to the bandwidth minimization problem. In the second case we show that the problem is equivalent to the natural generalization of the bandwidth problem and is closely approximated by the pathwidth. Also we show that the problem of computing the minimal robber's speed is NP-hard in both cases.

An O(n3) algorithm for finding a minimum weighted maximal irredundant set of interval graphs with vertices is presented. ? 1998 Elsevier Science B.V.

A homomorphism from a graph G to a graph H is locally bijective, surjective, or injective if its restriction to the neighborhood of every vertex of G is bijective, surjective, or injective, respectively. We prove that the problems of testing whether a given graph G allows a homomorphism to a given graph H that is locally bijective, surjective, or injective, respectively, are NP-complete, even when G has pathwidth at most 5, 4, or 2, respectively, or when both G and H have maximum degree 3. We complement these hardness results by showing that the three problems are polynomial-time solvable if G has bounded treewidth and in addition G or H has bounded maximum degree., An extended abstract of this paper appeared in the proceedings of FCT 2013, LNCS 8070: 121-132. http://dx.doi.org/10.1007/978-3-642-40164-0_14

We show that the question “Is a graph 3-colorable?” remains NP-complete when restricted to the class of triangle-free graphs with maximum degree 4. Likewise the question “Is a triangle-free graph k-colorable?” is shown to be NP-complete for any fixed value of k ⩾ 4.

The notion of k-limited packing in a graph is a generalization of 2-packing. For a given non negative integer k, a subset B of vertices is a k-limited packing if there are at most k elements of B in the closed neighborhood of every vertex. On the other side, a k-tuple domination set in a graph is a subset of vertices D such that every vertex has at least k elements of D in its closed neighborhood. In this work we first reveal a strong relationship between these notions, and obtain from a result due to Liao and Chang (2002), the polynomiality of the k-limited packing problem for strongly chordal graphs.We also prove that, in coincidence with the case of domination, the k-limited packing problem is NP-complete for split graphs. Finally, we prove that both problems are polynomial for the non-perfect class of P4-tidy graphs, including the perfect classes of P4-sparse graphs and cographs. Fil: Dobson, Maria Patricia. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Leoni, Valeria Alejandra. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Nasini, Graciela Leonor. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina

We prove three complexity results on vertex coloring problems restricted to $P_k$-free graphs, i.e., graphs that do not contain a path on $k$ vertices as an induced subgraph. First of all, we show that the pre-coloring extension version of 5-coloring remains NP-complete when restricted to $P_6$-ree graphs. Recent results of Hoàng et al. imply that this problem is polynomially solvable on $P_5$-free graphs. Secondly, we show that the pre-coloring extension version of 3-coloring is polynomially solvable for $P_6$-free graphs. This implies a simpler algorithm for checking the 3-colorability of $P_6$-free graphs than the algorithm given by Randerath and Schiermeyer. Finally, we prove that 6-coloring is NP-complete for $P_7$-free graphs. This problem was known to be polynomially solvable for $P_5$-free graphs and NP-complete for $P_8$-free graphs, so there remains one open case.

In 1997 Lampert and Slater introduced parallel knock-out schemes, an iterative process on graphs that goes through several rounds. In each round of this process, every vertex eliminates exactly one of its neighbors. The parallel knock-out number of a graph is the minimum number of rounds after which all vertices have been eliminated (if possible). The parallel knock-out number is related to well-known concepts like perfect matchings, hamiltonian cycles, and 2-factors.We derive a number of combinatorial and algorithmic results on parallel knock-out numbers: for families of sparse graphs (like planar graphs or graphs of bounded tree-width), the parallel knock-out number grows at most logarithmically with the number n of vertices; this bound is basically tight for trees. Furthermore, there is a family of bipartite graphs for which the parallel knock-out number grows proportionally to the square root of n. We characterize trees with parallel knock-out number at most 2, and we show that the parallel knock-out number for trees can be computed in polynomial time via a dynamic programming approach (whereas in general graphs this problem is known to be NP-hard). Finally, we prove that the parallel knock-out number of a claw-free graph is either infinite or less than or equal to 2.

We consider computational complexity questions related to parallel knock-out schemes for graphs. In such schemes, in each round, each remaining vertex of a given graph eliminates exactly one of its neighbours. We show that the problem of whether, for a given graph, such a scheme can be found that eliminates every vertex is NP-complete. Moreover, we show that, for all fixed positive integers k > 1, the problem of whether a given graph admits a scheme in which all vertices are eliminated in at most k rounds is NP-complete. For graphs with bounded tree-width, however, both of these problems are shown to be solvable in polynomial time.

The aim of edge modification problems is to change the edge set of a given graph as little as possible in order to satisfy a certain property. Edge modification problems in graphs have a lot of applications in different areas, and many polynomial-time algorithms and NP-completeness proofs for this kind of problems are known. In this work we prove new NP-completeness results for these problems in some graph classes, such as interval, circular-arc, permutation, circle, bridged, weakly chordal and clique-Helly graphs.

DNA graphs are the vertex induced subgraphs of De Bruijn graphs over a four letter alphabet. In this paper, we prove the NP-hardness of various recognition problems for subgraphs of De Bruijn graphs; in particular, the recognition of DNA graphs is shown to be NP-hard. As a consequence, two open questions from a recent paper by Błażewicz et al. (Discrete Appl. Math. 98, (1999) 1) are answered in the negative.

For a fixed integer r≥2, the K r -packing problem is to find the maximum number of pairwise vertex-disjointK r 's (complete graphs on r vertices) in a given graph. The K r -factor problem asks for the existence of a partition of the vertex set of a graph into K r 's. The K r -packing problem is a natural generalization of the classical matching problem, but turns out to be much harder for r≥3 – it is known that for r≥3 the K r -factor problem is NP-complete for graphs with clique number r [16]. This paper considers the complexity of the K r -packing problem on restricted classes of graphs. We first prove that for r≥3 the K r -packing problem is NP-complete even when restrict to chordal graphs, planar graphs (for r=3, 4 only), line graphs and total graphs. The hardness result for K 3-packing on chordal graphs answers an open question raised in [6]. We also give (simple) polynomial algorithms for the K 3-packing and the K r -factor problems on split graphs (this is interesting in light of the fact that K r -packing becomes NP-complete on split graphs for r≥4), and for the K r -packing problem on cographs.