Search

We define a proportionally dense subgraph (PDS) as an induced subgraph of a graph with the property that each vertex in the PDS is adjacent to proportionally as many vertices in the subgraph as in the graph. We prove that the problem of finding a PDS of maximum size is APX -hard on split graphs, and NP -hard on bipartite graphs. We also show that deciding if a PDS is inclusion-wise maximal is co-NP -complete on bipartite graphs. Nevertheless, we present a simple polynomial-time ( 2 − 2 Δ + 1 ) -approximation algorithm for the problem, where Δ is the maximum degree of the graph. Finally, we show that all Hamiltonian cubic graphs with n vertices (except two) have a PDS of size ⌊ 2 n + 1 3 ⌋ , which we prove to be an upper bound on the size of a PDS in cubic graphs.

We study approximation hardness of the Minimum Dominating Set problem and its variants in undirected and directed graphs. Using a similar result obtained by Trevisan for Minimum Set Cover we prove the first explicit approximation lower bounds for various kinds of domination problems (connected, total, independent) in bounded degree graphs. Asymptotically, for degree bound approaching infinity, these bounds almost match the known upper bounds. The results are applied to improve the lower bounds for other related problems such as Maximum Induced Matching and Maximum Leaf Spanning Tree.

We provide the first interesting explicit lower bounds on efficient approximability for two closely related optimization problems in graphs, MINIMUM EDGE DOMINATING SET and MINIMUM MAXIMAL MATCHING. We show that it is NP-hard to approximate the solution of both problems to within any constant factor smaller than $${\frac{7}{6}}$$ . The result extends with negligible loss to bounded degree graphs and to everywhere dense graphs.

In this paper we theoretically study the MINIMUM RANGE ASSIGNMENT problem in static ad-hoc networks with arbitrary structure, where the transmission distances can violate triangle inequality. We consider two versions of the MINIMUM RANGE ASSIGNMENT problem, where the communication graph has to fulfill either the h-strong connectivity condition (MIN-RANGE(h-SC)) or the h-broadcast condition (MIN-RANGE(h-B)). Both homogeneous and non-homogeneous cases are studied. By approximating arbitrary edge-weighted graphs by paths, we present probabilistic O(logn)-approximation algorithms for MIN-RANGE(h-SC)and MIN-RANGE(h-B), which improves the previous best ratios O(lognloglogn) and O(n^2lognloglogn), respectively [D. Ye, H. Zhang, The range assignment problem in static ad-hoc networks on metric spaces, Proceedings of the 11th Colloquium on Structural Information and Communication Complexity, Sirocco 2004, Lecture Notes in Computer Science, vol. 3104, pp. 291-302]. The result for MIN-RANGE(h-B)matches the lower bound [G. Rossi, The range assignment problem in static ad-hoc wireless networks. Ph.D. Thesis, 2003] for the case that triangle inequality for transmission distance holds (which is a special case of our model). Furthermore, we show that if the network fulfils certain property and the distance power gradient @a is sufficiently small, the approximation ratio is improved to O((loglogn)^@a). Finally we discuss the applications of our algorithms in mobile ad-hoc networks.

The MINIMUM 2SAT-DELETION problem is to delete the minimum number of clauses in a 2SAT instance to make it satisfiable. It is one of the prototypes in the approximability hierarchy of minimization problems Khanna et al. [Constraint satisfaction: the approximability of minimization problems, Proceedings of the 12th Annual IEEE Conference on Computational Complexity, Ulm, Germany, 24–27 June, 1997, pp. 282–296], and its approximability is largely open. We prove a lower approximation bound of View the MathML source8√5-15≈2.88854, improving the previous bound of View the MathML source10√5-21≈1.36067 by Dinur and Safra [The importance of being biased, Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), May 2002, pp. 33–42, also ECCC Report TR01-104, 2001]. For highly restricted instances with exactly four occurrences of every variable we provide a lower bound of View the MathML source 3/2. Both inapproximability results apply to instances with no mixed clauses (the literals in every clause are both either negated, or unnegated).We further prove that any k -approximation algorithm for the MINIMUM 2SAT-DELETION problem polynomially reduces to a (2-2/(k+1))(2-2/(k+1))-approximation algorithm for the MINIMUM VERTEX COVER problem.One ingredient of these improvements is our proof that the MINIMUM VERTEX COVER problem is hardest to approximate on graphs with perfect matching. More precisely, the problem to design a ρρ-approximation algorithm for the MINIMUM VERTEX COVER on general graphs polynomially reduces to the same problem on graphs with perfect matching. This improves also on the results by Chen and Kanj [On approximating minimum vertex cover for graphs with perfect matching, Proceedings of the 11st ISAAC, Taipei, Taiwan, Lecture Notes in Computer Science, vol. 1969, Springer, Berlin, 2000, pp. 132–143].

In this paper we study the Minimum Range Assignment problem in static ad-hoc networks with arbitrary structure, where the transmission distances can violate triangle inequality. We consider two versions of the Minimum Range Assignment problem, where the communication graph has to fulfill either the h-strong connectivity condition (Min-Range(h-SC)) or the h-broadcast condition (Min-Range(h-B)). Both homogeneous and non-homogeneous cases are studied. By approximating arbitrary edge-weighted graphs by paths, we present probabilistic O(log n)-approximation algorithms for Min-Range(h-SC) and Min-Range(h-B), which improves the previous best ratios O(log n loglog n) and O(n2log n loglog n), respectively [21]. The result for Min-Range(h-B) matches the lower bound [20] for the case that triangle inequality for transmission distance holds (which is a special case of our model). Furthermore, we show that if the network fulfils certain property and the distance power gradient α is sufficiently small, the approximation ratio is improved to O((loglog n)α).

We study approximation hardness of the Minimum Dominating Set problem and its variants in undirected and directed graphs. We state the first explicit approximation lower bounds for various kinds of domination problems (connected, total, independent) in bounded degree graphs. For most of dominating set problems we prove asymptotically almost tight lower bounds. The results are applied to improve the lower bounds for other related problems such as the Maximum Induced Matching problem and the Maximum Leaf Spanning Tree problem.

We obtain slightly improved upper bounds on efficient approximability of the Maximum Independent Set problem in graphs of maximum degree at most B (shortly, B-MaxIS), for small B≥ 3. The degree-three case plays a role of the central problem, as many of the results for the other problems use reductions to it. Our careful analysis of approximation algorithms of Berman and Fujito for 3-MaxIS shows that one can achieve approximation ratio arbitrarily close to \(3-\frac{\sqrt{13}}{2}\). Improvements of an approximation ratio below \(\frac65\) for this case translate to improvements below \(\frac{B+3}{5}\) of approximation factors for B-MaxIS for all odd B. Consequently, for any odd B≥ 3, polynomial time algorithms for B-MaxIS exist with approximation ratios arbitrarily close to \(\frac{B+3}5-\frac{4(5\sqrt{13}-18)}5\frac{(B-2)!!}{(B+1)!!}\). This is currently the best upper bound for B-MaxIS for any odd B, 3≤ B

The Minimum 2SAT-Deletion problem is to delete the minimum number of clauses in a 2SAT instance to make it satisfiable. It is one of the prototypes in the approximability hierarchy of minimization problems [8], and its approximability is largely open. We prove a lower approximation bound of \(8\sqrt 5-15\approx 2.88854\), improving the previous bound of \(10\sqrt5-21\approx 1.36067\) by Dinur and Safra [5]. For highly restricted instances with exactly 4 occurrences of every variable we provide a lower bound of \(\frac32\). Both inapproximability results apply to instances with no mixed clauses (the literals in every clause are both either negated, or unnegated).

We provide the first interesting explicit lower bounds on efficient approximability for two closely related optimization problems in graphs, MINIMUM EDGE DOMINATING SET and MINIMUM MAXIMAL MATCHING. We show that it is NP-hard to approximate the solution of both problems to within any constant factor smaller than 7/6. The result extends with negligible loss to bounded degree graphs and to everywhere dense graphs.

We study small degree graph problems such as Maximum Independent Set and Minimum Node Cover and improve approximation lower bounds for them and for a number of related problems, like Max- B -Set Packing, Min- B -Set Cover, Max-Matching in B-uniform 2-regular hypergraphs. For example, we prove NP-hardness factor of \(\frac{95}{94}\) for Max-3DM, and factor of \(\frac{48}{47}\) for Max-4DM; in both cases the hardness result applies even to instances with exactly two occurrences of each element.

The paper contributes to the systematic study (started by Berman and Karpinski) of explicit approximability lower bounds for small occurrence optimization problems.We present parametrized reductions for some packing and covering problems, including 3-Dimensional Matching, and prove the best known inapproximability results even for highly restricted versions of them. For example, we show that it is NP-hard to approximate Max-3-DM within 139/138 even on instances with exactly two occurrences of each element. Previous known hardness results for bounded occurence case of the problem required that the bound is at least three, and even then no explicit lower bound was known. New structural results which improve the known bounds for 3-regular amplifiers and hence the inapproximability results for numerous small occurrence problems studied earlier by Berman and Karpinski are also presented.