Abstract The (Perfect) Matching Cut problem is to decide if a connected graph has a (perfect) matching that is also an edge cut. The Disconnected Perfect Matching problem is to decide if a connected graph has a perfect matching that contains a matching cut. Both Matching Cut and Disconnected Perfect Matching are -complete for planar graphs of girth 5, whereas Perfect Matching Cut is known to be -complete even for subcubic bipartite graphs of arbitrarily large fixed girth. We prove that Matching Cut and Disconnected Perfect Matching are also -complete for bipartite graphs of arbitrarily large fixed girth and bounded maximum degree. Our result for Matching Cut resolves a 20-year old open problem. We also show that the more general problem d -Cut, for every fixed $$d\ge 1$$ d ≥ 1 , is -complete for bipartite graphs of arbitrarily large fixed girth and bounded maximum degree. Furthermore, we show that Matching Cut, Perfect Matching Cut and Disconnected Perfect Matching are -complete for H-free graphs whenever H contains a connected component with two vertices of degree at least 3. Afterwards, we update the state-of-the-art summaries for H-free graphs and compare them with each other, and with a known and full classification of the Maximum Matching Cut problem, which is to determine a largest matching cut of a graph G. Finally, by combining existing results, we obtain a complete complexity classification of Perfect Matching Cut for $$\mathcal{H}$$ H -subgraph-free graphs where $$\mathcal{H}$$ H is any finite set of graphs.

For an integer k ≥ 2, a k-community structure in an undirected graph is a partition of its vertex set into k sets called communities, each of size at least two, such that every vertex of the graph has proportionally at least as many neighbours in its own community as in any other community. In this paper, we give a necessary and sufficient condition for a forest on n vertices to admit a k-community structure. Furthermore, we provide an O(k2 ・ n2)-time algorithm that computes such a k-community structure in a forest, if it exists. These results extend a result of Bazgan et al., 2018. We also show that if communities are allowed to have size one, then every forest with n ≥ k ≥ 2 vertices admits a k-community structure that can be found in time O(k2 ・ n2). We then consider threshold graphs and show that every connected threshold graph admits a 2-community structure if and only if it is not isomorphic to a star; also if such a 2-community structure exists, we explain how to obtain it in linear time. We further describe an infinite family of disconnected threshold graphs, containing exactly one isolated vertex, that do not admit any 2-community structure. Finally, we present a new infinite family of connected graphs that may contain an even or an odd number of vertices without 2-community structures, even if communities are allowed to have size one.

In this paper, we consider the following two problems: (i) Deletion Blocker ( α ) where we are given an undirected graph G = ( V , E ) and two integers k , d ≥ 1 and ask whether there exists a subset of vertices S ⊆ V with | S | ≤ k such that α ( G − S ) ≤ α ( G ) − d , that is the independence number of G decreases by at least d after having removed the vertices from S ; (ii) Transversal ( α ) where we are given an undirected graph G = ( V , E ) and two integers k , d ≥ 1 and ask whether there exists a subset of vertices S ⊆ V with | S | ≤ k such that for every maximum independent set I we have | I ∩ S | ≥ d . We show that both problems are polynomial-time solvable in the class of co-comparability graphs by reducing them to the well-known Vertex Cut problem. Our results generalise a result of Chang et al. (2001) and a recent result of Hoang et al. (2023).

Matching cut Perfect matching 𝐻-free graph Diameter Radius DichotomyThe (Perfect) Matching Cut problem is to decide if a graph 𝐺 has a (perfect) matching cut, i.e., a (perfect) matching that is also an edge cut of 𝐺.Both Matching Cut and Perfect Matching Cut are known to be NP-complete.A perfect matching cut is also a matching cut with maximum number of edges.To increase our understanding of the relationship between the two problems, we perform a complexity study for the Maximum Matching Cut problem, which is to determine a largest matching cut in a graph.Our results yield full dichotomies of Maximum Matching Cut for graphs of bounded diameter, bounded radius and 𝐻-free graphs.A disconnected perfect matching of a graph 𝐺 is a perfect matching that contains a matching cut of 𝐺.We also show how our new techniques can be used for finding a disconnected perfect matching with a largest matching cut for special graph classes.In this way we can prove that the decision problem Disconnected Perfect Matching is polynomial-time solvable for (𝑃 6 + 𝑠𝑃 2 )-free graphs for every 𝑠 ≥ 0, extending a known result for 𝑃 5 -free graphs (Bouquet and Picouleau, 2020).

International audience

The (Perfect) Matching Cut problem is to decide if a graph $G$ has a (perfect) matching cut, i.e., a (perfect) matching that is also an edge cut of $G$. Both Matching Cut and Perfect Matching Cut are known to be NP-complete. A perfect matching cut is also a matching cut with maximum number of edges. To increase our understanding of the relationship between the two problems, we perform a complexity study for the Maximum Matching Cut problem, which is to determine a largest matching cut in a graph. Our results yield full dichotomies of Maximum Matching Cut for graphs of bounded diameter, bounded radius and $H$-free graphs. A disconnected perfect matching of a graph $G$ is a perfect matching that contains a matching cut of $G$. We also show how our new techniques can be used for finding a disconnected perfect matching with a largest matching cut for special graph classes. In this way we can prove that the decision problem Disconnected Perfect Matching is polynomial-time solvable for $(P_6+sP_2)$-free graphs for every $s\geq 0$, extending a known result for $P_5$-free graphs (Bouquet and Picouleau, 2020).

Abstract The well-known -complete problem Matching Cut is to decide if a graph has a matching that is also an edge cut of the graph. We prove new complexity results for Matching Cut restricted to H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. We also prove new complexity results for two recently studied variants of Matching Cut, on H-free graphs. The first variant requires that the matching cut must be extendable to a perfect matching of the graph. The second variant requires the matching cut to be a perfect matching. In particular, we prove that there exists a small constant $$r>0$$ r > 0 such that the first variant is -complete for $$P_r$$ P r -free graphs. This addresses a question of Bouquet and Picouleau (The complexity of the Perfect Matching-Cut problem. CoRR, arXiv:2011.03318 , (2020)). For all three problems, we give state-of-the-art summaries of their computational complexity for H-free graphs.

In this paper, we consider the problem of reducing the semitotal domination number of a given graph by contracting k edges, for some fixed k≥1. We show that this can always be done with at most 3 edge contractions and further characterise those graphs requiring 1, 2 or 3 edge contractions, respectively, to decrease their semitotal domination number. We then study the complexity of the problem for k=1 and obtain in particular a complete complexity dichotomy for monogenic classes.

We continue the study initiated by Bonomo-Braberman and Gonzalez in 2020 on $r$-locally checkable problems. We propose a dynamic programming algorithm that takes as input a graph with an associated clique-width expression and solves a $1$-locally checkable problem under certain restrictions. We show that it runs in polynomial time in graphs of bounded clique-width, when the number of colors of the locally checkable problem is fixed. Furthermore, we present a first extension of our framework to global properties by taking into account the sizes of the color classes, and consequently enlarge the set of problems solvable in polynomial time with our approach in graphs of bounded clique-width. As examples, we apply this setting to show that, when parameterized by clique-width, the $[k]-$Roman domination problem is FPT, and the $k$-community problem, Max PDS and other variants are XP.

Perfect Matching-Cut is the problem of deciding whether a graph has a perfect matching that contains an edge-cut. We show that this problem is NP-complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite five-regular graphs, for graphs of diameter three and for bipartite graphs of diameter four. We show that there exist polynomial time algorithms for the following classes of graphs: claw-free, $P_5$-free, diameter two, bipartite with diameter three and graphs with bounded tree-width.

For a connected graph G=(V,E), a matching M⊆E is a matching cut of G if G−M is disconnected. It is known that for an integer d, the corresponding decision problem Matching Cut is polynomial-time solvable for graphs of diameter at most d if d≤2 and NP-complete if d≥3. We prove the same dichotomy for graphs of bounded radius. For a graph H, a graph is H-free if it does not contain H as an induced subgraph. As a consequence of our result, we can solve Matching Cut in polynomial time for P6-free graphs, extending a recent result of Feghali for P5-free graphs. We then extend our result to hold even for (sP3+P6)-free graphs for every s≥0 and initiate a complexity classification of Matching Cut for H-free graphs.

In this paper we continue the systematic study of Contact graphs of Paths on a Grid (CPG graphs) initiated in Deniz et al. (2018). A CPG graph is a graph for which there exists a collection of pairwise interiorly disjoint paths on a grid in one-to-one correspondence with its vertex set such that two vertices are adjacent if and only if the corresponding paths touch at a grid-point. If every such path has at most k bends for some k≥0, the graph is said to be Bk-CPG. We first show that, for any k≥0, the class of Bk-CPG graphs is strictly contained in the class of Bk+1-CPG graphs even within the class of planar graphs, thus implying that there exists no k≥0 such that every planar CPG graph is Bk-CPG. The main result of the paper is that recognizing CPG graphs and Bk-CPG graphs with k≥1 is NP-complete. Moreover, we show that the same remains true even within the class of planar graphs in the case k≥3. We then consider several graph problems restricted to CPG graphs and show, in particular, that Independent Set and Clique Cover remain NP-hard for B0-CPG graphs. Finally, we consider the related classes Bk-EPG of edge-intersection graphs of paths with at most k bends on a grid. Although it is possible to optimally color a B0-EPG graph in polynomial time, as this class coincides with that of interval graphs, we show that, in contrast, 3-Colorability is NP-complete for B1-EPG graphs.

In this note, we consider the following problem: given a connected graph G, can we reduce the domination number of G by using only one edge contraction? We show that the problem is polynomial-time solvable on (P3+kP2)-free graphs for any k≥0 which can be combined with former results to obtain a complexity dichotomy of the problem on H-free graphs.

In this paper, we study the problem of deciding whether the total domination number of a given graph G can be reduced using exactly one edge contraction (called 1-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.

A semitotal dominating set of a graph G with no isolated vertex is a dominating set D of G such that every vertex in D is within distance two of another vertex in D. The minimum size γt2(G) of a semitotal dominating set of G is squeezed between the domination number γ(G) and the total domination number γt(G). Semitotal Dominating Set is the problem of finding, given a graph G, a semitotal dominating set of G of size γt2(G). In this paper, we continue the systematic study on the computational complexity of this problem when restricted to special graph classes. In particular, we show that it is solvable in polynomial time for the class of graphs of bounded mim-width by a reduction to Total Dominating Set and we provide several approximation lower bounds for subclasses of subcubic graphs. Moreover, we obtain complexity dichotomies in monogenic classes for the decision versions of Semitotal Dominating Set and Total Dominating Set. Finally, we show that it is NP-complete to recognise the graphs such that γt2(G)=γt(G) and those such that γ(G)=γt2(G), even if restricted to be planar and with maximum degree at most 4, and we provide forbidden induced subgraph characterisations for the graphs hereditarily satisfying either of these two equalities.

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 {P_6,P_4+P_2}-free graphs and that it is coNP-hard when restricted to subcubic claw-free graphs and 2P_3-free graphs. As a consequence, we are able to establish a complexity dichotomy for the problem on H-free graphs when H is connected.

In this paper, we study the following problem: given a connected graph $G$, can we reduce the domination number of $G$ by at least one using $k$ edge contractions, for some fixed integer $k \geq 0$? We present positive and negative results regarding the computational complexity of this problem.

Hajirasouliha and Raphael (WABI 2014) proposed a model for deconvoluting mixed tumor samples measured from a collection of high-throughput sequencing reads. This is related to understanding tumor evolution and critical cancer mutations. In short, their formulation asks to split each row of a binary matrix so that the resulting matrix corresponds to a perfect phylogeny and has the minimum number of rows among all matrices with this property. In this paper, we disprove several claims about this problem, including an NP-hardness proof of it. However, we show that the problem is indeed NP-hard, by providing a different proof. We also prove NP-completeness of a variant of this problem proposed in the same paper. On the positive side, we propose an efficient (though not necessarily optimal) heuristic algorithm based on coloring co-comparability graphs, and a polynomial time algorithm for solving the problem optimally on matrix instances in which no column is contained in both columns of a pair of conflicting columns. Implementations of these algorithms are freely available at https://github.com/alexandrutomescu/MixedPerfectPhylogeny.

We consider the problem of covering the edges of a graph by a sequence of matchings subject to the constraint that each edge e appears in at least a given fraction r ( e ) of the matchings. Although it can be determined in polynomial time whether such a sequence of matchings exists or not [Grötschel et al., Combinatorica (1981), 169–197], we show that several questions about the length of the sequence are computationally intractable. Therefore, as is commonly done [Golumbic, Algorithmic graph theory and perfect graphs, 2004], we restrict our investigation to a special class of graphs. In recent work [Birand et al., INFOCOM 2010 Proceedings, 2010], two of the authors dealt with so‐called OLoP ( Overall Local Pooling ) graphs, a class of graphs for which similar matching‐related problems are tractable (namely, in an online distributed wireless network scheduling setting). We therefore focus on these graphs and generalize the results to a larger class of graphs which we call GOLoP graphs. In particular, we show that deciding whether a given GOLoP graph has a matching sequence of length at most k can be done in linear time. In case the answer is affirmative, we show how to construct, in quadratic time, the matching sequence of length at most k . Finally, we prove that, for GOLoP graphs, the length of a shortest sequence does not exceed a constant times the least common denominator of the fractions r ( e ), leading to a pseudopolynomial‐time algorithm for minimizing the length of the sequence. We show that the constant equals 1 for OLoP graphs and, following Seymour [Seymour, Proc. London Math. Soc., 1979], conjecture that the constant is as small as 2 for general graphs. We then show that this conjecture holds for all graphs with at most 10 vertices. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol 62(3), 165–182 2013

Efficient operation of wireless networks and switches requires using simple (and in some cases distributed) scheduling algorithms. In general, simple greedy algorithms (known as Greedy Maximal Scheduling, or GMS) are guaranteed to achieve only a fraction of the maximum possible throughput (e.g., 50% throughput in switches). However, it was recently shown that in networks in which the Local Pooling conditions are satisfied, GMS achieves 100% throughput. Moreover, in networks in which the σ-Local Pooling conditions hold, GMS achieves σ% throughput. In this paper, we focus on identifying the specific network topologies that satisfy these conditions. In particular, we provide the first characterization of all the network graphs in which Local Pooling holds under primary interference constraints (in these networks, GMS achieves 100% throughput). This leads to a linear-time algorithm for identifying Local-Pooling-satisfying graphs. Moreover, by using similar graph-theoretical methods, we show that in all bipartite graphs (i.e., input-queued switches) of size up to 7 ×n, GMS is guaranteed to achieve 66% throughput, thereby improving upon the previously known 50% lower bound. Finally, we study the performance of GMS in interference graphs and show that in certain specific topologies, its performance could be very bad. Overall, the paper demonstrates that using graph-theoretical techniques can significantly contribute to our understanding of greedy scheduling algorithms.

Efficient operation of wireless networks and switches requires using simple (and in some cases distributed) scheduling algorithms. In general, simple greedy algorithms (known as Greedy Maximal Scheduling - GMS) are guaranteed to achieve only a fraction of the maximum possible throughput (e.g., 50% throughput in switches). However, it was recently shown that in networks in which the Local Pooling conditions are satisfied, GMS achieves 100% throughput. Moreover, in networks in which the ¿-Local Pooling conditions hold, GMS achieves ¿% throughput. In this paper, we focus on identifying the specific network topologies that satisfy these conditions. In particular, we provide the first characterization of all the network graphs in which Local Pooling holds under primary interference constraints (in these networks GMS achieves 100% throughput). This leads to a linear time algorithm for identifying Local Pooling-satisfying graphs. Moreover, by using similar graph theoretical methods, we show that in all bipartite graphs (i.e., input-queued switches) of size up to 7 × n, GMS is guaranteed to achieve 66% throughput, thereby improving upon the previously known 50% lower bound. Finally, we study the performance of GMS in interference graphs and show that in certain specific topologies its performance could be very bad. Overall, the paper demonstrates that using graph theoretical techniques can significantly contribute to our understanding of greedy scheduling algorithms.

Abstract An extension of the basic image reconstruction problem in discrete tomography is considered: given a graph G = (V,E) and a family $\cal {P}$ of chains Pi together with vectors h(Pi) = (h ,…,h ), one wants to find a partition V1,…,Vk of V such that for each Pi and each color j, |Vj ∩ Pi| = h . An interpretation in terms of scheduling is presented. We consider special cases of graphs and identify polynomially solvable cases; general complexity results are established in this case and also in the case where V1,…,Vk is required to be a proper vertex k‐coloring of G. Finally, we examine also the case of (proper) edge k‐colorings and determine its complexity status. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008