Search

12th International Symposium on Parameterized and Exact Computation (IPEC 2017); International audience; Given a graph G, we define bcg(G) as the minimum k for which G can be contracted to the uniformly triangulated grid Γk. A graph class G has the SQGC property if every graph G ∈ G has treewidth O(bcg(G)c) for some 1 ≤ c < 2. The SQGC property is important for algo- rithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a general family of graph classes that satisfy the SQGC property and includes bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for several intersection graph classes of 2-dimensional geometrical objects.

It is widely accepted that necessity comes in different varieties, often called ‘kinds': metaphysical necessity, logical necessity, natural necessity, conceptual necessity, moral necessity, to name but a few – and the same goes for the varieties of possibility. What is usually not fully appreciated, however, is that modal variety is not simply ‘unidimensional': it does not only involve one main variable – kind, whose values are the particular kinds of necessity. Rather, I argue, it is ‘bidimensional', involving two distinct variables – domain and strength. In the first part of the paper, I introduce and develop the proposed bidimensional picture of modal variety, defending it against the common, unidimensional one. In the second part, I consider how the main available accounts of necessities and their relations rely, at least to a significant extent, on the latter picture, pointing out important limitations that they face as a result. I also show how, accordingly, alternative accounts based on a clear and systematic distinction between domain and strength would overcome those limitations. I conclude that, beyond the particular bidimensionalist view defended, our understanding of the modal realm may benefit from more direct debate on whether and how it is multidimensional.

Bidimensionality Theory was introduced by [E.D. Demaine, F.V. Fomin, M.Hajiaghayi, and D.M. Thilikos. Subexponential parameterized algorithms on graphs of bounded genus and H-minor-free graphs, J. ACM, 52 (2005), pp.866--893] as a tool to obtain sub-exponential time parameterized algorithms on H-minor-free graphs. In [E.D. Demaine and M.Hajiaghayi, Bidimensionality: new connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2005, pp.590--601] this theory was extended in order to obtain polynomial time approximation schemes (PTASs) for bidimensional problems. In this work, we establish a third meta-algorithmic direction for bidimensionality theory by relating it to the existence of linear kernels for parameterized problems. In particular, we prove that every minor (respectively contraction) bidimensional problem that satisfies a separation property and is expressible in Countable Monadic Second Order Logic (CMSO), admits a linear kernel for classes of graphs that exclude a fixed graph (respectively an apex graph) H as a minor. Our results imply that a multitude of bidimensional problems g graph classes. For most of these problems no polynomial kernels on H-minor-free graphs were known prior to our work., Comment: An an earlier version of this paper appeared in SODA 2010. That paper contained preliminary versions of some of the results of this paper

Due to the wide use of internet, electronic commerce market is gradually increasing but consumers still conceive various transaction-related problems. Various studies argue that those problems are obstructing trust in electronic commerce. Most studies on electronic commerce address that trust is measured as a Single dimension in which factors obstructing trust are same as those of increasing distrust. However, this study doesn`t view trust as a single dimensional level but understands trust and distrust are bidimensional. This study also holds a viewpoint that they are influenced by different antecedents. According to the results of empirical analysis, the antecedents of trust have a significant explanatory power to trust and those of distrust have it to distrust. Other relations among the notions of trust and distrust, perceived risk and purchase intention as depicted in the research model are all statistically significant except the relation between distrust and purchase intention. This study shows a strong evidence of the bidimensionality of trust with separate antecedents.

Our newly developing theory of bidimensional graph problems provides general techniques for designing efficient fixed-parameter algorithms and approximation algorithms for NP-hard graph problems in broad classes of graphs. This theory applies to graph problems that are bidimensional in the sense that (1) the solution value for the k × k grid graph (and similar graphs) grows with k, typically as Ω(k2), and (2) the solution value goes down when contracting edges and optionally when deleting edges. Examples of such problems include feedback vertex set, vertex cover, minimum maximal matching, face cover, a series of vertex-removal parameters, dominating set, edge dominating set, r-dominating set, connected dominating set, connected edge dominating set, connected r-dominating set, and unweighted TSP tour (a walk in the graph visiting all vertices). Bidimensional problems have many structural properties; for example, any graph embeddable in a surface of bounded genus has treewidth bounded above by the square root of the problem's solution value. These properties lead to efficient---often subexponential---fixed-parameter algorithms, as well as polynomial-time approximation schemes, for many minor-closed graph classes. One type of minor-closed graph class of particular relevance has bounded local treewidth, in the sense that the treewidth of a graph is bounded above in terms of the diameter; indeed, we show that such a bound is always at most linear. The bidimensionality theory unifies and improves several previous results. The theory is based on algorithmic and combinatorial extensions to parts of the Robertson-Seymour Graph Minor Theory, in particular initiating a parallel theory of graph contractions. The foundation of this work is the topological theory of drawings of graphs on surfaces and our results regarding the relation (the linearity) of the size of the largest grid minor in terms of treewidth in bounded-genus graphs and more generally in graphs excluding a fixed graph H as a minor. In this thesis, we also develop the algorithmic theory of vertex separators, and its relation to the embeddings of certain metric spaces. Unlike in the edge case, we show that embeddings into L1 (and even Euclidean embeddings) are insufficient, but that the additional structure provided by many embedding theorems does suffice for our purposes. We obtain an O( logn ) approximation for min-ratio vertex cuts in general graphs, based on a new semidefinite relaxation of the problem, and a tight analysis of the integrality gap which is shown to be Θ( logn ). We also prove various approximate max-flow/min-vertex-cut theorems, which in particular give a constant-factor approximation for min-ratio vertex cuts in any excluded-minor family of graphs. Previously, this was known only for planar graphs, and for general excluded-minor families the best-known ratio was O(log n). These results have a number of applications. We exhibit an O( logn ) pseudo-approximation for finding balanced vertex separators in general graphs. Furthermore, we obtain improved approximation ratios for treewidth: In any graph of treewidth k, we show how to find a tree decomposition of width at most O(k logk ), whereas previous algorithms yielded O( k log k). For graphs excluding a fixed graph as a minor, we give a constant-factor approximation for the treewidth; this via the bidimensionality theory can be used to obtain the first polynomial-time approximation schemes for problems like minimum feedback vertex set and minimum connected dominating set in such graphs. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)

In this paper we make the first step beyond bidimensionality by obtaining subexponential time algorithms for problems on directed graphs. We develop two different methods to achieve subexponential time parameterized algorithms for problems on sparse directed graphs. We exemplify our approaches with two well studied problems. For the first problem, $k$-Leaf Out-Branching, which is to find an oriented spanning tree with at least $k$ leaves, we obtain an algorithm solving the problem in time $2^{\cO(\sqrt{k} \log k)} n+ n^{\cO(1)}$ on directed graphs whose underlying undirected graph excludes some fixed graph $H$ as a minor. For the special case when the input directed graph is planar, the running time can be improved to $2^{\cO(\sqrt{k} )}n + n^{\cO(1)}$. The second example is a generalization of the {\sc Directed Hamiltonian Path} problem, namely $k$-Internal Out-Branching, which is to find an oriented spanning tree with at least $k$ internal vertices. We obtain an algorithm solving the problem in time $2^{\cO(\sqrt{k} \log k)} + n^{\cO(1)}$ on directed graphs whose underlying undirected graph excludes some fixed apex graph $H$ as a minor. Finally, we observe that for any $\ve>0$, the $k$-Directed Path problem is solvable in time $\cO((1+\ve)^k n^{f(\ve)})$, where $f$ is some function of $\ve$. Our methods are based on non-trivial combinations of obstruction theorems for undirected graphs, kernelization, problem specific combinatorial structures and a layering technique similar to the one employed by Baker to obtain PTAS for planar graphs.

We provide new combinatorial theorems on the structure of graphs that are contained as contractions in graphs of large treewidth. As a consequence of our combinatorial results we unify and significantly simplify contraction bidimensionality theory—the meta algorithmic framework to design efficient parameterized and approximation algorithms for contraction closed parameters.

Robertson and Seymour developed the seminal Graph MinorTheory over the past two decades. This breakthrough in graph structuretheory tells us that a very wide family of graph classes (anything closedunder deletion and contraction) have a rich structure similar to planargraphs. This structure has many algorithmic applications that have becomeincreasingly prominent over the past decade. For example, Fellowsand Langston showed in 1988 that it immediately leads to a wealth of(nonconstructive) fixed-parameter algorithms. One recent approach to algorithmic graph minor theory is "bidimensionalitytheory". This theory provides general tools for designing fast(constructive, often subexponential) fixed-parameter algorithms, and approximationalgorithms (often PTASs), for a wide variety of NP-hard graph problems in graphs excluding a fixed minor. For example, some ofthe most general algorithms for feedback vertex set and connected dominatingset are based on bidimensionality. Another approach is "deletionand contraction decompositions", which split any graph excluding a fixedminor into a bounded number of small-treewidth graphs. For example,this approach has led to some of the most general algorithms for graphcoloring and the Traveling Salesman Problem on graphs. I will describethese and other approaches to efficient algorithms through graph minors.

This paper surveys the theory of bidimensional graph problems. We summarize the known combinatorial and algorithmic results of this theory, the foundational Graph Minor results on which this theory is based, and the remaining open problems.

Let be a finite collection of geometric (not necessarily convex) bodies in the plane. Clearly, this class of geometric objects naturally generalizes the class of disks, lines, ellipsoids, and even convex polygons. We consider geometric intersection graphs where each body of the collection is represented by a vertex, and two vertices of are adjacent if the intersection of the corresponding bodies is non-empty. For such graph classes and under natural restrictions on their maximum degree or subgraph exclusion, we prove that the relation between their treewidth and the maximum size of a grid minor is linear. These combinatorial results vastly extend the applicability of all the meta-algorithmic results of the bidimensionality theory to geometrically defined graph classes. © 2014 Springer International Publishing Switzerland.

The manifestation of bidimensionality in T -, T ′-, and T * -type structures of A 2 B O 4 oxides occurs in terms of cooperative structure–bonding properties involving both the metal–oxygen A ( B )–O bonds and the A – A cationic repulsions. The analysis of the A -metal network gives evidence of ninefold cationic coordination very similar to the ninefold oxygen coordination. The short A – A apical distance results in A – A repulsions which are able to balance the A –O apical overbonding. In La 2 NiO 4 as compared to La 2 CuO 4 , the contribution of these repulsions is more important ( d A – A =3.25 A in La 2 NiO 4 ; 3.66 A in La 2 CuO 4 ). The perovskite (P)/rock salt (RS) intergrowth, T -type structure, due to strong geometrical constraint, has excess anisotropy which needs to be relieved. In contrast, the perovskite (P)/calcium fluoride (CF), T ′- type structure, is nearly free from any excess anisotropy to be relieved. In the (P)/(RS)/(P)/(CF) intergrowth, T * -type structure, owing to a more regular distribution of the A –O bonds, the excess anisotropy is further restricted. Crystal chemical mechanisms such as A substitutions and the oxidation of Cu, which lower the excess charge in the anionic and cationic (P) and (RS) slabs, respectively, do not operate. The useful role of controlled excess structure–bonding anisotropy is emphasized.

Bidimensionality theory provides a general framework for developing subexponential fixed parameter algorithms for NP-hard problems. A representative example of such algorithms is the one for the longest path problem in planar graphs. The largest grid minor and the branch-decomposition of a graph play an important role in bidimensionality theory. The best known approximation algorithm for computing the largest grid minor of a planar graph has the approximation ratio 3. In this thesis, we report a computational study on a branch-decomposition based algorithm for the longest path problem in planar graphs. We implement the 3-approximation algorithm for computing large grid minors. We also design and implement an exact algorithm for computing the largest cylinder minor in planar graphs to evaluate the practical performance of the 3-approximation algorithm. The results show that the bidimensional framework is practical for the longest path problem in planar graphs.

Bidimensionality theory is a powerful framework for the development of metaalgorithmic techniques. It was introduced by Demaine et al. as a tool to obtain sub-exponential time parameterized algorithms for problems on H-minor free graphs. Demaine and Hajiaghayi extended the theory to obtain PTASs for bidimensional problems, and subsequently improved these results to EPTASs. Fomin et. al related the theory to the existence of linear kernels for parameterized problems. In this paper we revisit bidimensionality theory from the perspective of approximation algorithms and redesign the framework for obtaining EPTASs to be more powerful, easier to apply and easier to understand. Two of the most widely used approaches to obtain PTASs on planar graphs are the Lipton-Tarjan separator based approach, and Baker's approach. Demaine and Hajiaghayi strengthened both approaches using bidimensionality and obtained EPTASs for a multitude of problems. We unify the two strenghtened approaches to combine the best of both worlds. At the heart of our framework is a decomposition lemma which states that for "most" bidimensional problems, there is a polynomial time algorithm which given an H-minor-free graph G as input and an e > 0 outputs a vertex set X of size e * OPT such that the treewidth of G n X is f(e). Here, OPT is the objective function value of the problem in question and f is a function depending only on e. This allows us to obtain EPTASs on (apex)-minor-free graphs for all problems covered by the previous framework, as well as for a wide range of packing problems, partial covering problems and problems that are neither closed under taking minors, nor contractions. To the best of our knowledge for many of these problems including cycle packing, vertex-h-packing, maximum leaf spanning tree, and partial r-dominating set no EPTASs on planar graphs were previously known.

In this paper we use several of the key ideas from Bidimensionality to give a new generic approach to design EPTASs and subexponential time parameterized algorithms for problems on classes of graphs which are not minor closed, but instead exhibit a geometric structure. In particular we present EPTASs and subexponential time parameterized algorithms for Feedback Vertex Set, Vertex Cover, Connected Vertex Cover, Diamond Hitting Set, on map graphs and unit disk graphs, and for Cycle Packing and Minimum-Vertex Feedback Edge Set on unit disk graphs. Our results are based on the recent decomposition theorems proved by Fomin et al [SODA 2011], and our algorithms work directly on the input graph. Thus it is not necessary to compute the geometric representations of the input graph. To the best of our knowledge, these results are previously unknown, with the exception of the EPTAS and a subexponential time parameterized algorithm on unit disk graphs for Vertex Cover, which were obtained by Marx [ESA 2005] and Alber and Fiala [J. Algorithms 2004], respectively. We proceed to show that our approach can not be extended in its full generality to more general classes of geometric graphs, such as intersection graphs of unit balls in R^d, d >= 3. Specifically we prove that Feedback Vertex Set on unit-ball graphs in R^3 neither admits PTASs unless P=NP, nor subexponential time algorithms unless the Exponential Time Hypothesis fails. Additionally, we show that the decomposition theorems which our approach is based on fail for disk graphs and that therefore any extension of our results to disk graphs would require new algorithmic ideas. On the other hand, we prove that our EPTASs and subexponential time algorithms for Vertex Cover and Connected Vertex Cover carry over both to disk graphs and to unit-ball graphs in R^d for every fixed d.

We provide new combinatorial theorems on the structure of graphs that are contained as contractions in graphs of large treewidth. As a consequence of our combinatorial results we unify and significantly simplify contraction bidimensionality theory-the meta algorithmic framework to design efficient parameterized and approximation algorithms for contraction closed parameters. © 2009 Springer Berlin Heidelberg.

Control of structure and order in oxides is essential for the design of new superconducting cuprates. The intergrowth of perovskite and rock salt layers, as found in bismuth, thallium and, very recently, the record breaking mercury cuprates, is just one way to induce bidimensionality. Defect “all perovskite” oxides, such as Ln2Ba2C2Ti2O11 (Ln = La, Nd, Eu) are discussed as examples of a crystal -chemical approach to the induction of bidimensionality and order in mixed perovskite oxides of copper., This work was supported by the spanish CICYT (MAT90-1020-C02-01) and the MIDAS Program (92–1592). We thank the Departament ďEnsenyament de la Generalitat de Catalunya for a predoctoral fellowship awarded to M. R. P.

We prove the following theorem. Given a planar graph $G$ and an integer $k$, it is possible in polynomial time to randomly sample a subset $A$ of vertices of $G$ with the following properties: (i) $A$ induces a subgraph of $G$ of treewidth $\mathcal{O}(\sqrt{k}\log k)$, and (ii) for every connected subgraph $H$ of $G$ on at most $k$ vertices, the probability that $A$ covers the whole vertex set of $H$ is at least $(2^{\mathcal{O}(\sqrt{k}\log^2 k)}\cdot n^{\mathcal{O}(1)})^{-1}$, where $n$ is the number of vertices of $G$. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound $2^{\mathcal{O}(\sqrt{k} \log^2 k)} n^{\mathcal{O}(1)}$. The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph, examples of such problems include Directed $k$-Path, Weighted $k$-Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.

International audience; For a fixed connected graph H, the {H}-M-Deletion problem asks, given a graph G, for the minimum number of vertices that intersect all minor models of H in G. It is known that this problem can be solved in time f (tw) · n O(1) , where tw is the treewidth of G. We determine the asymptotically optimal function f (tw), for each possible choice of H. Namely, we prove that, under the ETH, f(tw) = 2Θ(tw) if H is a contraction of the chair or the banner, and f(tw) = 2Θ(tw·log tw) otherwise. Prior to this work, such a complete characterization was only known when H is a planar graph with at most five vertices. For the upper bounds, we present an algorithm in time 2Θ(tw·log tw) ·nO(1) for the more general problem where all minor models of connected graphs in a finite family F need to be hit. We combine several ingredients such as the machinery of boundaried graphs in dynamic programming via representatives, the Flat Wall Theorem, Bidimensionality, the irrelevant vertex technique, treewidth modulators, and protrusion replacement. In particular, this algorithm vastly generalizes a result of Jansen et al. [SODA 2014] for the particular case F = {K5, K3,3}. For the lower bounds, our reductions are based on a generic construction building on the one given by the authors in [IPEC 2018], which uses the framework introduced by Lokshtanov et al. [SODA 2011] to obtain superexponential lower bounds.

Two of the most widely used approaches to obtain polynomial-time approximation schemes (PTASs) on planar graphs are the Lipton-Tarjan separator-based approach and Baker’s approach. In 2005, Demaine and Hajiaghayi strengthened both approaches using bidimensionality and obtained efficient polynomial-time approximation schemes (EPTASs) for several problems, including C onnected D ominating S et and F eedback V ertex S et . In this work, we unify the two strengthened approaches to combine the best of both worlds. We develop a framework allowing the design of EPTAS on classes of graphs with the subquadratic grid minor (SQGM) property. Roughly speaking, a class of graphs has the SQGM property if, for every graph G from the class, the fact that G contains no t × t grid as a minor guarantees that the treewidth of G is subquadratic in t . For example, the class of planar graphs and, more generally, classes of graphs excluding some fixed graph as a minor, have the SQGM property. At the heart of our framework is a decomposition lemma stating that for “most” bidimensional problems on a graph class G with the SQGM property, there is a polynomial-time algorithm that, given a graph G ϵ G as input and an ϵ > 0, outputs a vertex set X of size ϵ ċ OPT such that the treewidth of G - X is f (ϵ). Here, OPT is the objective function value of the problem in question and f is a function depending only on ϵ. This allows us to obtain EPTASs on (apex)-minor-free graphs for all problems covered by the previous framework as well as for a wide range of packing problems, partial covering problems and problems that are neither closed under taking minors nor contractions. To the best of our knowledge, for many of these problems—including C ycle P acking , F -P acking , F -D eletion , M ax L eaf S panning T ree , or P artial r -D ominating S et —no EPTASs, even on planar graphs, were previously known. We also prove novel excluded grid theorems in unit disk and map graphs without large cliques. Using these theorems, we show that these classes of graphs have the SQGM property. Based on the developed framework, we design EPTASs and subexponential time parameterized algorithms for various classes of problems on unit disk and map graphs.

International audience; In parameterized complexity, a {\em kernelization algorithm} can be seen as a reduction of a parameterized problem to itself, so that the produced equivalent instance has size depending exclusively on the parameter. If this size is polynomial, then then we say that the parameterized problem in question admits a polynomial kernelization algorithm. Kernelization can be seen as a formalization of the notion of preprocessingand has occupied a big part of the research on Multi-variate Algorithmics. The first algorithmic meta-theorem on kernelizationappeared in \href{https://arxiv.org/pdf/0904.0727}{\green{[{\sl H.~L. Bodlaender, F.~V. Fomin, D.~Lokshtanov, E.~Penninkx, S.~Saurabh, and D.~M. Thilikos. (Meta) kernelization. J. {ACM}, 63(5):44:1--44:69, 2016}\,]}} and unified a large family of previously known kernelization results on problems defined on topologically embeddable graphs.In this exposition we present the central results of this paper. During our presentation we pay attention to the abstractions on which the results where founded and take into account the subsequent advancements on this topic.

Let G be a graph of order n . A subset S of V ( G ) is a dominating set of G if every vertex in V ( G ) ⧹ S is adjacent to at least one vertex of S . The domination polynomial of G is the polynomial D ( G , x ) = ∑ i = γ ( G ) n d ( G , i ) x i , where d ( G , i ) is the number of dominating sets of G of size i , and γ ( G ) is the size of a smallest dominating set of G , called the domination number of G . We say two graphs G and H are dominating equivalent if D ( G , x ) = D ( H , x ) . A graph G is said to be dominating unique , or simply D -unique, if D ( H , x ) = D ( G , x ) implies that H ≅ G . The goal of this paper is to find a new approach to determine the dominating uniqueness of graphs. In this paper, we define a new graph polynomial, called star polynomial, and introduced an analogy notion of star uniqueness of graphs. As an application, if G is a graph without isolated vertices, we show that a graph G is star unique if and only if G ‾ ∨ K m is dominating unique for each m ⩾ 0 . As a by-product, the dominating uniqueness of many families of dense graphs is also determined.

We consider boolean linear programming formulations of the independent set, the vertex and the edge dominating set problems and prove their polynomial-time solvability for classes of graphs with (augmented) constraint matrices having bounded minors in the absolute value.

A total dominating set of an undirected graph G=(V,E) is a set SV of vertices such that each vertex of G is adjacent to at least one vertex of S. A secure total dominating set of G is a set DV of vertices such that D is a total dominating set of G and each vertex vVD is adjacent to at least one vertex uD with the property that the set (D{u}){v} is a total dominating set of G. The secure total domination number st(G) of G is the minimum cardinality of a secure total dominating set of G. We establish bounds on the secure total domination number. In particular, we show that every graph G with no isolated vertices satisfies st(G)2(G), where (G) is the independence number of G. Further, we study the problem of finding the secure total domination number. We show that the decision version of the problem is NP-complete for chordal bipartite graphs, planar bipartite graphs with arbitrary large girth and maximum degree 3, split graphs and graphs of separability at most 2. Finally, we show that the optimisation version of the problem can be approximated in polynomial time within a factor of cln|V| for some constant c>1 and cannot be approximated in polynomial time within a factor of cln|V| for some constant c

A connected dominating set in a graph is a dominating set of vertices that induces a connected subgraph. Following analogous studies in the literature related to independent sets, dominating sets, and total dominating sets, we study in this paper the class of graphs in which the connected dominating sets can be separated from the other vertex subsets by a linear weight function. More precisely, we say that a graph is connected-domishold if it admits non-negative real weights associated to its vertices such that a set of vertices is a connected dominating set if and only if the sum of the corresponding weights exceeds a certain threshold. We characterize the graphs in this non-hereditary class in terms of a property of the set of minimal cutsets of the graph. We give several characterizations for the hereditary case, that is, when each connected induced subgraph is required to be connected-domishold. The characterization by forbidden induced subgraphs implies that the class properly generalizes two well known classes of chordal graphs, the block graphs and the trivially perfect graphs. Finally, we study certain algorithmic aspects of connected-domishold graphs. Building on connections with minimal cutsets and properties of the derived hypergraphs and Boolean functions, we show that our approach leads to new polynomially solvable cases of the weighted connected dominating set problem., 32 pages, 8 figures

A set D of vertices in a graph G = ( V , E ) is called a 2-point set dominating set of G if for every set T ⊆ V − D there exists a non-empty set S ⊆ D containing at most two vertices such that the induced subgraph 〈 S ∪ T 〉 is connected. A set D ⊆ V ( G ) is called a global 2-point set dominating set of G if D is a 2-point set dominating set of both G and G ‾ . The global 2-point set domination number (2-point set domination number) is the minimum cardinality of a global 2-point set dominating set (2-point set dominating set) in G. In this paper we determine bounds on the global 2-point set domination number of a graph in terms of other graph invariants. We have also given relation between global 2-point set domination number and 2-point set domination number for some classes of graphs.