In: European Journal of Operational Research, 2011, vol. 210, no. 2, p. 169-175
Given a graph G =(V, E), a satisfying bisection of G is a partition of the vertex set V into two sets V1, V2, such that |V1| = |V2|, and such that every vertex v in V has at least as many neighbors in its own set as in the other set. The problem of deciding whether a graph G admits such a partition is NP-complete. In Bazgan et al. (2008) [C. Bazgan, Z. Tuza, D. Vanderpooten, Approximation of...
|
In: Networks, 2008, vol. 51, no. 4, p. 256-267
An extension of the basic image reconstruction problem in discrete tomography is considered: given a graph G = (V,E) and a family equation image of chains Pi together with vectors h(Pi) = (h1, . . . , hik), one wants to find a partition V1,…,Vk of V such that for each Pi and each color j, |Vj ∩ Pi| = hij. An interpretation in terms of scheduling is presented. We consider special cases of...
|
In: Graphs and Combinatorics, 2007, vol. 23, no. 1, p. 47-60
We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with n nodes on each side, we give sufficient conditions for the existence of a set R with |R| = n + 1 such that perfect matchings with k red edges exist for all k, 0 ≤ k ≤ n. Given two integers p...
|
In: Discrete Mathematics, 2009, vol. 309, p. 4306-4314
Given an undirected graph G=(V,E) with matching number \nu(G), we define d- blockers as subsets of edges B such that \nu(G=(V,E\B))\leq \nu(G)-d. We define d- transversals T as subsets of edges such that every maximum matching M has |M\cap T|\geq d. We explore connections between d-blockers and d-transversals. Special classes of graphs are examined which include complete graphs, regular...
|
In: Discrete Mathematics, 2010, vol. 310, p. 132-146
Given an undirected graph G=(V,E) with matching number \nu(G), a d-blocker is a subset of edges B such that \nu(/V,E\B))= d. While the associated decision problem is NP-complete in bipartite graphs we show how to construct efficiently minimum d-transversals and minimum d-blockers in the...
|
In: 30th International Symposium on Algorithms and Computation (ISAAC) - Leibniz International Proceedings in Informatics, 2019, vol. 149, no. 21, p. 1-14
In this paper, we consider the following problem: given a connected graph G, can we reduce the domination number of G by one by using only one edge contraction? We show that the problem is NP-hard when restricted to {P6, P4 + P2}-free graphs and that it is coNP-hard when restricted to subcubic claw-free graphs and 2P3-free graphs. As a consequence, we are able to establish a complexity dichotomy...
|
In: Lecture Notes in Computer Science, 2017, vol. 10185, p. 470-483
Let d and k be two given integers, and let G be a graph. Can we reduce the independence number of G by at least d via at most k graph operations from some fixed set S? This problem belongs to a class of so-called blocker problems. It is known to be co-NP-hard even if S consists of either an edge contraction or a vertex deletion. We further investigate its computational complexity under these...
|
In: Theoretical Computer Science, 2021, vol. 877, p. 18-35
In this paper, we study the problem of deciding whether the total domination number of a given graph Gcan be reduced using exactly one edge contraction (called1-Edge Contraction(γt)). We focus on several graph classes and determine the computational complexity of this problem. By putting together these results, we manage to obtain a complete complexity dichotomy for H-free graphs.
|
In: Lecture Notes in Computer Science, 2016, vol. 9843, p. 229-240
An upper dominating set in a graph is a minimal (with respect to set inclusion) dominating set of maximum cardinality. The problem of finding an upper dominating set is generally NP-hard, but can be solved in polynomial time in some restricted graph classes, such as P4-free graphs or 2K2-free graphs. For classes defined by finitely many forbidden induced subgraphs, the boundary separating...
|
In: Lecture Notes in Computer Science, 2018, vol. 10856, p. 89-100
A graph G is a Bo- VPG graph if it is the vertex intersection graph of horizontal and vertical paths on a grid. A graph G is a contact Bo- VPG graph if the vertices can be represented by interiorly disjoint horizontal or vertical paths on a grid and two vertices are adjacent if and only if the corresponding paths touch. In this paper, we present a minimal forbidden induced subgraph...
|
