A matching is said to be disconnected if the saturated vertices induce a disconnected subgraph and induced if the saturated vertices induce a 1-regular graph. The disconnected and induced matching numbers are defined as the maximum cardinality of such matchings, respectively, and are known to be NP-hard to compute. In this paper, we study the relationship between these two parameters and the matching number. In particular, we discuss the complexity of two decision problems; first: deciding if the matching number and disconnected matching number are equal; second: deciding if the disconnected matching number and induced matching number are equal. We show that given a bipartite graph with diameter four, deciding if the matching number and disconnected matching number are equal is NP-complete; the same holds for bipartite graphs with maximum degree three. We characterize diameter three graphs with equal matching number and disconnected matching number, which yields a polynomial time recognition algorithm. Afterwards, we show that deciding if the induced and disconnected matching numbers are equal is co-NP-complete for bipartite graphs of diameter 3. When the induced matching number is large enough compared to the maximum degree, we characterize graphs where these parameters are equal, which results in a polynomial time algorithm for bounded degree graphs.

One way to define the Matching Cut problem is: Given a graph G, is there an edge-cut M of G such that M is an independent set in the line graph of G? We propose the more general Conflict-Free Cut problem: Together with the graph G, we are given a so-called conflict graph Gˆ on the edges of G, and we ask for an edge-cutset M of G that is independent in Gˆ. Since conflict-free settings are popular generalizations of classical optimization problems and Conflict-Free Cut was not considered in the literature so far, we start the study of the problem. We show that the problem is NP-complete even when the maximum degree of G is 5 and Gˆ is 1-regular. The same reduction implies an exponential lower bound on the solvability based on the Exponential Time Hypothesis. We also give parameterized complexity results: We show that the problem is fixed-parameter tractable with the vertex cover number of G as a parameter, and we show W[1]-hardness even when G has a feedback vertex set of size one, and the clique cover number of Gˆ is the parameter. Since the clique cover number of Gˆ is an upper bound on the independence number of Gˆ and thus the solution size, this implies W[1]-hardness when parameterized by the cut size. We list polynomial-time solvable cases and interesting open problems. At last, we draw a connection to a symmetric variant of SAT.

The Independent Cutset problem asks whether there is a set of vertices in a given graph that is both independent and a cutset. This problem is -complete even when the input graph is planar and has maximum degree five. We first present a O ⁎ ( 1.4423 n ) -time algorithm to compute a minimum independent cutset (if any). Since the property of having an independent cutset is MSO 1 -expressible, our main results are concerned with structural parameterizations for the problem considering parameters incomparable with clique-width. We present -time algorithms under the following parameters: the dual of the maximum degree, the dual of the solution size, the size of a dominating set (where a dominating set is given as an additional input), the size of an odd cycle transversal, the distance to chordal graphs, and the distance to P 5 -free graphs. We close by introducing the notion of α -domination, which generalizes key ideas of this article.

The previously fastest algorithm for deciding the existence of an independent cut had a runtime of O * ( 1 . 4423 n ) , where n is the order of the input graph. We improve this to O * ( 1 . 4143 n ) . In fact, we prove a runtime of O * ( 2 ( 1 2 − α Δ ) n ) on graphs of order n and maximum degree at most Δ , where α Δ = 1 2 + 4 ⌊ Δ 2 ⌋ . Furthermore, we show that the problem is fixed-parameter tractable on graphs of order n and minimum degree at least β n for some β > 1 2 , where β is the parameter.

Kanté and Nourine [ SIAM J. Discrete Math., 30 (2016), pp. 311--326] present a polynomial time algorithm for the computation of the hull number of chordal graphs. We point out a gap in the correctness proof of their algorithm for chordal graphs and show that computing the hull number of a chordal graph is NP-hard, which most likely rules out the existence of a polynomial time algorithm.

The traditional Erdos-Renyi model of a random network is of little use in modelling the type of complex networks which modern researchers study. In this graph, every pair of vertices is equally likely to be connected by an edge. However, 21st century networks are of diverse nature and usually exhibit inhomogeneity among their nodes. This motivates the study, for a fixed degree sequence D=(d1, ..., dn), of a uniformly chosen simple graph G(D) on {1, ..., n} where the vertex i has degree di. In this paper, we study the existence of a giant component in G(D). A heuristic argument suggests that a giant component in G(D) will exist provided that the sum of the squares of the degrees is larger than twice the sum of the degrees. In 1995, Molloy and Reed essentially proved this to be the case when the degree sequence D under consideration satisfies certain technical conditions [Random Structures & Algorithms, 6:161-180]. This work has attracted considerable attention, has been extended to degree sequences under weaker conditions and has been applied to random models of a wide range of complex networks such as the World Wide Web or biological systems operating at a sub-molecular level. Nevertheless, the technical conditions on D restrict the applicability of the result to sequences where the vertices of high degree play no important role. This is a major problem since it is observed in many real-world networks, such as scale-free networks, that vertices of high degree (the so-called hubs) are present and play a crucial role. In this paper we characterize when a uniformly random graph with a fixed degree sequence has a giant component. Our main result holds for every degree sequence of length n provided that a minor technical condition is satisfied. The typical structure of G(D) when D does not satisfy this condition is relatively simple and easy to understand. Our result gives a unified criterion that implies all the known results on the existence of a giant component in G(D), including both the generalizations of the Molloy-Reed result and results on more restrictive models. Moreover, it turns out that the heuristic argument used in all the previous works on the topic, does not extend to general degree sequences.

We study perfect matchings in graphs that have the two properties of being robust as well as recoverable; where robust means that the failure of a set of not too many edges of can be compensated, and recoverable means that this compensation can be done in an efficient way, that is, has a perfect matching for which the symmetric difference of and is small. We establish the hardness of several related algorithmic problems and identify some tractable cases. Among others we show the hardness of the well known matching preclusion number of a graph. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(3), 210–213 2015

We prove that a cubic graph with $m$ edges has an induced matching with at least $m/9$ edges. Our result generalizes a result for planar graphs due to Kang, Mnich, and Müller (SIAM J. Discrete Math., 26 (2012), pp. 1383--1411) and solves a conjecture of Henning and Rautenbach.

Let $G$ be a graph of order $n$. Let $\mathrm{lpt}(G)$ be the minimum cardinality of a set $X$ of vertices of $G$ such that $X$ intersects every longest path of $G$, and define $\mathrm{lct}(G)$ analogously for cycles instead of paths. We prove that $\mathrm{lpt}(G)\leqslant \lceil\frac{n}{4}-\frac{n^{2/3}}{90}\rceil$ if $G$ is connected, and $\mathrm{lct}(G)\leqslant \lceil\frac{n}{3}-\frac{n^{2/3}}{36}\rceil$ if $G$ is $2$-connected. Our bound on $\mathrm{lct}(G)$ improves an earlier result of Thomassen. Furthermore, we prove upper bounds on $\mathrm{lpt}(G)$ for planar graphs and graphs of bounded tree-width.

We study the graphs $G$ for which the hull number $h(G)$ and the geodetic number $g(G)$ with respect to $P_3$-convexity coincide. These two parameters correspond to the minimum cardinality of a set $U$ of vertices of $G$ such that the simple expansion process which iteratively adds to $U$ all vertices outside of $U$ having two neighbors in $U$ produces the whole vertex set of $G$ either eventually or after one iteration, respectively. We establish numerous structural properties of the graphs $G$ with $h(G)=g(G)$, allowing for the constructive characterization as well as the efficient recognition of all such graphs that are triangle-free. Furthermore, we characterize---in terms of forbidden induced subgraphs---the graphs $G$ that satisfy $h(G')=g(G')$ for every induced subgraph $G'$ of $G$.

Let $G$ be a finite, simple, and undirected graph and let $S$ be a set of vertices of $G$. If no vertex of $G$ that does not belong to $S$ has two neighbors in $S$, then $S$ is $P_3$-convex. The $P_3$-convex hull $H_G(S)$ of $S$ is the smallest $P_3$-convex set containing $S$. The $P_3$-Carathéodory number of $G$ is the smallest integer $c$ such that for every set $S$ and every vertex $u$ in $H_G(S)$, there is a set $F\subseteq S$ with $|F|\leq c$ and $u\in H_G(F)$. We study structural and algorithmic aspects of the $P_3$-Carathéodory number. We characterize the $P_3$-Carathéodory number of trees and block graphs, establish upper bounds on the $P_3$-Carathéodory number of general graphs and of claw-free graphs, and prove that it is NP-complete to decide for a given bipartite graph $G$ and a given integer $k$ whether the $P_3$-Carathéodory number of $G$ is at least $k$.

For \documentclass{article} \usepackage{amsmath,amsfonts,amssymb}\pagestyle{empty}\begin{document} $n\in \mathbb{N}$ \end{document} and \documentclass{article} \usepackage{amsmath,amsfonts,amssymb}\pagestyle{empty}\begin{document} $D\subseteq \mathbb{N}$ \end{document}, the distance graph P has vertex set {0,1,…,n − 1} and edge set {ij | 0 ≤ i,j ≤ n − 1,|j − i| ∈ D}. The class of distance graphs generalizes the important and very well-studied class of circulant graphs, which have been proposed for numerous network applications. In view of fault tolerance and delay issues in these applications, the connectivity and diameter of circulant graphs have been studied in great detail. Our contributions are hardness results concerning computational problems related to the connectivity and the diameter of distance graphs and a characterization of the connected distance graphs P for |D| = 2. © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(4), 310-315 2011

For a graph $G=(V,E)$ we consider vertex–k-labellings $f:V\to\{1,2,\dots,k\}$ for which the induced edge weighting $w:E\to\{2,3,\dots,2k\}$ with $w(uv)=f(u)+f(v)$ is injective or surjective or both. We study the relation between these labellings and the number theoretic notions of an additive basis and a Sidon set, present a new construction for a so-called restricted additive basis, and derive the corresponding consequences for the labellings. We prove that a tree of order n and maximum degree $\Delta$ has a vertex–k-labelling f for which w is bijective if and only if $\Delta\leq k=n/2$. Using this result we prove a recent conjecture of Ivančo and Jendroł concerning edge-irregular total labellings for graphs that are sparse enough.

A set of vertices C in a graph is convex if it contains all vertices which lie on shortest paths between vertices in C. The convex hull of a set of vertices S is the smallest convex set containing S. The hull number $h(G)$ of a graph G is the smallest cardinality of a set of vertices whose convex hull is the vertex set of G. For a connected triangle-free graph G of order n and diameter d at least 4, we prove that $h(G)\leq(n-d+3)/3$ if G has minimum degree at least 3 and that $h(G)\leq2(n-d+5)/7$, if G is cubic. Furthermore for a connected graph G of order n, girth g at least 5, minimum degree at least 2, and diameter d, we prove $h(G)\leq2+(n-d-1)/\left\lceil\frac{g-1}{2}\right\rceil$. All bounds are best possible.

We present a very fast algorithm for buffering repeater trees. We scan a given preliminary topology in a bottom-up fashion and insert buffers and inverters, respecting the parities of the sinks. Information obtained by preprocessing allows for very fast decisions. To bound the number of shielding repeaters, they are only used where necessary to maximize the worst slack. Furthermore, instead of using a fixed set of repeater positions, they are computed on the fly based on the already buffered subtrees. Another key feature of our algorithm is that we modify the preliminary topology while buffering in order to avoid parallel wires or too many inverters.

Abstract We study graphs G = (V,E) containing a long cycle which for given integers a1, a2,…,ak ∈ \input amssym ${\Bbb N}$ have an edge cut whose removal results in k components with vertex sets V1,V2,…,Vk such that |Vi| ≥ ai for 1 ≤ i ≤ k. Our results closely relate to problems and recent research in network sharing and network reliability. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

We present an implementation of an algorithm for constructing provably fast circuits for a class of Boolean functions with input signals that have individual starting times. We show how to adapt this algorithm to logic optimization for timing correction at late stages of VLSI physical design and report experimental results on recent industrial chips. By restructuring long critical paths, our code achieves worst-slack improvements of up to several hundred picoseconds on top of traditional timing optimization techniques.

The BonnTools provide innovative solutions for layout and timing closure that are used for many of the most complex integrated circuits. During 20 years of cooperation between the University of Bonn and IBM, new mathematical foundations and algorithms have been developed for the need of new technologies and leading-edge designs. In this paper we present the main ideas for placement, routing, timing optimization, and clock tree synthesis, which are the foundation of a continuing success story

We present a very fast algorithm for topology generation of repeater trees. Based on the criticality of the individual sinks, which is estimated taking their required signal arrival times and their distance from the root of the repeater tree into account, this topology connects very critical sinks in such a way as to maximize the minimum slack and to minimize wiring for non-critical sinks.We establish theoretical bounds on the optimum solution and prove that our algorithm produces results that are close to optimum with respect to slack and wirelength. Experimental results on industrial designs in 130 nm and 90 nm technologies demonstrate the excellent quality of our algorithm. Moreover, one million nontrivial repeater tree topologies are constructed in less than one minute of computing time.

The MIX technique forms the basis of many popular services that offer anonymity of communication in open and shared networks such as the Internet. In this paper, fundamental limits on the anonymity provided by the MIX technique are found by considering two different settings. First, we consider an information theoretic setting to determine the extent of information inherent in observations of the traffic passing through the MIX. We show that if the size of sender anonymity sets is less than the total user population, the information contained in traffic observations is sufficient to deduce all communication relationships between senders and receivers using the MIX. More importantly, we show that even if every user sends a message in each communication round, it is possible to compromise the anonymity significantly. We precisely characterize the extent of compromised anonymity in each case. In the second setting, we assume that the attacker has unlimited computational resources and is free to choose any attack algorithm. We derive tight upper and lower bounds on the minimum number of observations required to deduce all recipient peer-partners of a targeted user. The analysis done in these two settings reveals many discrete mathematical structures inherent in anonymity sets, and the intuition gained from these structures can be used when designing or using a MIX based anonymity technique.

The band-, tree-, and clique-width are of primary importance in algorithmic graph theory due to the fact that many problems that are NP-hard for general graphs can be solved in polynomial time when restricted to graphs where one of these parameters is bounded. It is known that for any fixed $\Delta \geq 3$, all three parameters are unbounded for graphs with vertex degree at most $Delta$. In this paper, we distinguish representative subclasses of graphs with bounded vertex degree that have bounded band-, tree-, or clique-width. Our proofs are constructive and lead to efficient algorithms for a variety of NP-hard graph problems when restricted to those classes.