Let k >= 1. A graph G is W-k if for any k pairwise disjoint independent vertex subsets A(1), ... A(k) in G, there exist k pairwise disjoint maximum independent sets S-1, ..., S-k in G such that A(i) subset of S-i f...
详细信息
Let k >= 1. A graph G is W-k if for any k pairwise disjoint independent vertex subsets A(1), ... A(k) in G, there exist k pairwise disjoint maximum independent sets S-1, ..., S-k in G such that A(i) subset of S-i for i is an element of [k]. Recognizing W-1 graphs is coNP-hard, as shown by Chvatal and Slater (1993) and, independently, by Sankaranarayana and Stewart (1992). Extending this result and answering a recent question of Levit and Tankus, we show that recognizing W-k graphs is coNP-hard for k >= 2. On the positive side, we show that recognizing W-k graphs is, for each k >= 2, fpt parameterized by clique-width and by tree-width. Finally, we construct graphs G that are not W-2 such that, for every vertex v in G and every maximal independent set S in G-N[nu], the largest independent set in N(nu)\S consists of a single vertex, thereby refuting a conjecture of Levit and Tankus.
A mixed dominating set is a set of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for MIXED DOMINATING SET, resolving some open quest...
详细信息
A mixed dominating set is a set of vertices and edges that dominates all vertices and edges of a graph. We study the complexity of exact and parameterized algorithms for MIXED DOMINATING SET, resolving some open questions. In particular, we settle the problem's complexity parameterized by treewidth and pathwidth by giving an algorithm running in time O* (5(tw)) (improving the current best O* (6(tw))), and a lower bound showing that our algorithm cannot be improved under the Strong Exponential Time Hypothesis (SETH), even if parameterized by pathwidth (improving a lower bound of O* ((2 - epsilon)(pw))). Furthermore, by using a simple but so far overlooked observation on the structure of minimal solutions, we obtain branching algorithms which improve the best known fpt algorithm for this problem, from O* (4.172(k)) to O* (3.510(k)), and the best known exact algorithm, from O* (2(n)) and exponential space, to O* (1.912(n)) and polynomial space.
We study the parameterized complexity of the problems of determining whether a graph contains a k-edge subgraph (k-vertex induced subgraph) that is a Pi-graph for Pi-graphs being one of the following four classes of g...
详细信息
We study the parameterized complexity of the problems of determining whether a graph contains a k-edge subgraph (k-vertex induced subgraph) that is a Pi-graph for Pi-graphs being one of the following four classes of graphs: Eulerian graphs, even graphs, odd graphs, and connected odd graphs. We also consider the parameterized complexity of their parametric dual problems. For these sixteen problems, we show that eight of them are fixed parameter tractable and four are W[1]-hard. Our main techniques are the color-coding method of Alon, Yuster and Zwick, and the random separation method of Cai, Chan and Chan. (C) 2011 Elsevier B.V. All rights reserved.
Given a graph G and a pair (F-1, F-2) of graph families, the function GDISJ(G),(F1), (F2) takes as input, two induced subgraphs G(1) and G(2) Of G, such that G(1) is an element of F-1 and G2 is an element of F-2 and r...
详细信息
Given a graph G and a pair (F-1, F-2) of graph families, the function GDISJ(G),(F1), (F2) takes as input, two induced subgraphs G(1) and G(2) Of G, such that G(1) is an element of F-1 and G2 is an element of F-2 and returns 1 if V(G(1)) boolean AND v (G(2)) = theta and 0 otherwise. We study the communication complexity of this problem in the two-party model. In particular, we look at pairs of hereditary graph families. We show that the communication complexity of this function, when the two graph families are hereditary, is sublinear if and only if there are finitely many graphs in the intersection of these two families. Then, using concepts from parameterized complexity, we obtain nuanced upper bounds on the communication complexity of GDISJ(G),(F1),(F2). A concept related to communication protocols is that of a (F-1, F-2)-separating family of a graph G. A collection F of subsets of V(G) is called a (F-1, F-2)-separating family for G, if for any two vertex disjoint induced subgraphs G(1) is an element of F-1 and G2 is an element of F-2, there is a set F is an element of F with V (G(1)) subset of F and V (G(2)) boolean AND F = theta. Given a graph G on n vertices, for any pair (F-1, F-2) of hereditary graph families with sublinear communication complexity for GDISJ(G),(F1),(F2), we, we give an enumeration algoritlun that finds a subexponential sized (F-1, F-2)-separating family. In fact, we give an enumeration algoritlun that finds a 2(o(k))n(O(1)) sized(F-1, F-2)-separating family, where k denotes the size of a minimtun sized set S of vertices such that V(G) \ S has a bipartition (V-1, V-2) with G[V-1] is an element of F-1 and G[V-2] is an element of F-2. We exhibit a wide range of applications for these separating families, to obtain combinatorial bounds, entuneration algorithms, as well as exact and FPI algorithms for several problems.
For a finite set Gamma of Boolean relations, MAX ONES SAT(Gamma) and EXACT ONES SAT(Gamma) are generalized satisfiability problems where every constraint relation is from Gamma, and the task is to find a satisfying as...
详细信息
For a finite set Gamma of Boolean relations, MAX ONES SAT(Gamma) and EXACT ONES SAT(Gamma) are generalized satisfiability problems where every constraint relation is from Gamma, and the task is to find a satisfying assignment with at least/exactly k variables set to 1, respectively. We study the parameterized complexity of these problems, including the question whether they admit polynomial kernels. For MAX ONES SAT(Gamma), we give a classification into five different complexity levels: polynomial-time solvable, admits a polynomial kernel, fixed-parameter tractable, solvable in polynomial time for fixed k, and NP-hard already for k = 1. For EXACT ONES SAT(Gamma), we refine the classification obtained earlier by taking a closer look at the fixed-parameter tractable cases and classifying the sets Gamma for which EXACT ONES SAT(Gamma) admits a polynomial kernel.
In the directed co-graph edge-deletion problem, we are given a directed graph and an integer k, and the question is whether we can delete, at most, k edges so that the resulting graph is a directed co-graph. In this p...
详细信息
In the directed co-graph edge-deletion problem, we are given a directed graph and an integer k, and the question is whether we can delete, at most, k edges so that the resulting graph is a directed co-graph. In this paper, we make two minor contributions. Firstly, we show that the problem is NP-hard. Then, we show that directed co-graphs are fully characterized by eight forbidden structures, each having, at most, six edges. Based on the symmetry properties and several refined observations, we develop a branching algorithm with a running time of O(2.733k), which is significantly more efficient compared to the brute-force algorithm, which has a running time of O(6k).
暂无评论