# Tag Info

9

This problem is called minimum palindromic factorization and this problem can be solved in $O(n \log n)$ time, see for example: A subquadratic algorithm for minimum palindrome factorization by Fici et al EERTREE: An Efficient Data Structure for Processing Palindromes in Strings by Rubinchik and Shur.

8

The problem is polynomial-time solvable. Say that a vertex is balanced if its in-degree equals its out-degree. Note that a directed graph is Eulerian iff every vertex is balanced and its underlying undirected graph is connected. Now, a directed graph is a vertex-disjoint union of Eulerian graphs iff every vertex is balanced. So, the problem amounts to ...

5

Here is the proof of Petrank's reduction. This was suggested to me by Édouard Bonnet. I still do not know whether this can be turned into an L-reduction. Suppose there is a PTAS algorithm $\mathscr{A}$ for MAX k VERTEX COVER, thus giving a $(1-\varepsilon)$-factor-approximate solution on a cubic graph $G=(V,E)$ with $|V|=n, |E|=m=3n/2$. We can use $\... 4 (Comment$\rightarrow$Answer) Consider the following algorithms for a hypergraph$(U,\mathcal S)$, with$n=|U|$: For a set$X\subseteq \mathcal S$of sets and a set$A \in X$, define$d_X(A)$as the number of elements in$A$that are double covered by$X$, i.e.$|A \cap \left(\bigcup(X \setminus \{A\})\right|$. Additionally, let$c(X)$denote the number ... 4 Yes, people do consider these problems but there is no standard name. A useful way to think about these problems is via packing integer programs. Consider the problem$\max wx$such that$Ax \le b, x \in {0,1}^n$where$A$is a$m \times n$non-negative matrix. The width of the program is$\min_{i,j} b_i/A_{i,j}$(which we can assume is at least$1$). If$A$... 4 Consider a graph on vertex set$V_1\cup V_2\cup V_3\cup V_4\cup \{a,b,c,d\}$where$|V_1|=|V_2|=|V_3|=|V_4|=n$. The edge set$E$is covered by$C=\{V_1\cup\{a,c\},V_2\cup\{a,d\},V_3\cup\{b,c\},V_4\cup\{b,d\},\{a,b\},\{c,d\}\}$. When$n$is large enough, any minimalist cover must contain the four maximum cliques$V_1\cup\{a,c\}$and so on, so it is not hard ... 3 Let$N(n)$be the number of triangles needed to cover$K_n$. Because every triangle covers only three of the$n\choose 2$edges, we have$\frac{1}{3}{n\choose 2}\leq N(n)$as a lower bound. Note that the case$n=2$is degenerate, as$K_2$has only one edge and no triangles. In the following analysis, I will allow myself to use triangles that cover only one ... 3 I don't know of a name, but your problem generalizes the notoriously hard Min-Rep problem (introduced in this paper by Kortsarz). Roughly, an input to Min-Rep consists of a bipartite graph$G=(A;B,E)$, with each of$A$and$B$sub-partitioned into a collection of equal-sized so-called supervertices. A superedge between two supervertices$a,b$is the set ... 3 ...aha, found it! This is the bipartite dimension problem, and yes it is NP-hard without further assumptions. Previously asked here: https://cs.stackexchange.com/questions/49266/finding-a-minimal-cover-of-a-subset-of-a-finite-cartesian-product-by-cartesian-p 2 The problem of covering$n$points in the Euclidean plane by$k$unit balls is a special case of your problem that is already known to be NP-complete. It is also hard to approximate the optimal covering radius better than a factor of about 1.84. See N. Megiddo and K.J. Supowit. On the complexity of some common geometric loca- tion problems. SIAM J. Comput., ... 2 This problem is known to be NP-complete (since the 1970s). Dyer and Frieze established its NP-hardness even for the highly restricted special case where the graph$G$is planar and bipartite: Martin E. Dyer, Alan M. Frieze: On the complexity of partitioning graphs into connected subgraphs. Discrete Applied Mathematics 10(2): 139-153 (1985) 2 Look up the concept of anticodes. Some bounds exist. Also if you have a linear$t-$error correcting code over$GF(q)$with length$n$and covering radius$r$and use homogeneity under translations by adding vectors$n-d=n-2t-1$would seem to be your answer but I haven't checked carefully. Cohen and Litsyn have a book on covering codes. A Simple ... 1 If$n$is congruent to$1$or$3$modulo$6$, there is a covering of the complete graph$K_n$with triangles so that each edge is used exactly in exactly one triangle, so this uses exactly$\frac{1}{3}\binom{n}{2}$triangles. This is called a Steiner triple system and the answers to this Math Overflow question give some ways to construct Steiner triple ... 1 For the case of disks in the plane, there is a recent PTAS: https://arxiv.org/abs/1607.06665 There is also a fixed parameter tractable algorithm for this problem for spaces with bounded VC dimension - see ref in the paper. For general metric spaces, it is easy to reduce the problem to set cover instance, where there is a cover with k sets covering m points,... 1 Your first problem is more or less in-approximable. It contains "Independent Set" as a special case. For a graph$G=(V,E)$, define your ground set as$U:=V$and for every vertex$v\in V$construct a corresponding subset$S_v$in your set system that contains the (closed) neighborhood of$v$. Then finding a cardinality-$k$independent set in$G$is equivalent ... 1 Problem 1 is known as SET PACKING. Like other packing problems, it's annoyingly hard. The best known bound is a$O(\sqrt{|S|})\$ approximation and it is indeed APX-hard.

Only top voted, non community-wiki answers of a minimum length are eligible