21

The cycle cover problem (CC) is the problem of finding a spanning set of cycles in a given directed or undirected input graph. If all the cycles in the cover must consist of at least $k$ edges/arcs, the resulting restriction of the problem is denoted $k$-UCC (in undirected graphs) and $k$-DCC (in directed graphs). The complexity of the directed version is ...


17

For $n$ uniformly random points in a unit square the number of components is $$\frac{3\pi}{8\pi+3\sqrt{3}}n+o(n)$$ See Theorem 2 of D. Eppstein, M. S. Paterson, and F. F. Yao (1997), "On nearest-neighbor graphs", Disc. Comput. Geom. 17: 263–282, https://www.ics.uci.edu/~eppstein/pubs/EppPatYao-DCG-97.pdf For points in any fixed higher dimension it is $\...


13

I can prove that no 4-regular graphs are 3-acyclic colorable. Consider a 4-regular graph with a 3-coloring. If we call the colors $a, b, c$, then one of the three subgraphs generated by restricting to either $a$ and $b$ colored vertices, $a$ and $c$ vcertices, or $b$ and $c$ vertices must have as many edges as vertices. But all graphs with as many edges as ...


12

This is not possible in general. The 4-cycle is actually helpful to consider: embedding it in $\mathbb{R}^k$ in the way you describe requires the images of all four vertices to be coplanar, forming a square (since the distances between adjacent vertices must be $1$ and those between the non-adjacent pairs must be $\sqrt{2}$). Now consider the complete ...


12

The problem is very similar to Min Uncut. In Min Uncut, given a graph $G = (V, E)$, we need to find a subset of edges $E'$ s.t. $G - E'$ is bipartite; the objective is to minimize the size of $|E'|$. For brevity, let me call you problem $\cal P$ and Min Uncut $\cal U$. Observation. An instance $G$ of $\cal P$ has a solution of cost 0 if and only if $G$ is ...


10

EDIT 2: Made explicit the underlying non-asymptotic bounds in the calculation. EDIT: Replaced the calculation for two dimensions by the case of arbitrary constant dimension. Added a table of the values. I'd like to add an informal sketch of how David's very elegant result can be calculated. (To be clear, I suggest selecting his answer as the "correct&...


8

The famous graph (the complement of the disjoint union of $n/3$ triangles) with $3^{n/3}$ maximal cliques is $K_1 \cup K_2$-free, and thus has none of $2C_4$, $C_5$, $P_5$ as an induced subgraph. https://doi.org/10.1007/BF02760024


7

The two-connected series-parallel DAGs are also called 2-terminal series-parallel graphs. The graph in the figure is also known as Wheatstone graph and is known as the example graph for demonstrating Braess' paradox in algorithmic game theory. It was shown [1, Theorem 5.3] that a DAG is 2-terminal series-parallel if and only if it does not contain a subgraph ...


6

Answering my own question: the answer is "no". For each $k \ge 3$, Ding and Oporowski construct a graph $G_k$ on $2k$ vertices with treewidth $3$, such that in every optimal tree decomposition of $G_k$ there is a vertex which is in at least $2k-2$ bags (see Figure 1 in their paper). Ding, Guoli; Oporowski, Bogdan, Some results on tree decomposition of ...


6

Theorem 1. The given problem is NP-hard, by reduction from MAX-CUT. Proof. Call the given problem Positive Discrepancy Cut (PDC). Define weighted PDC to be the generalization where the input is a graph $G=(V,E)$ with polynomially bounded (possibly negative) integer edge weights, and the goal is to determine whether there is a positive-weight cut. To prove ...


6

The strategy I outlined in the comment worked: reading through Bodirsky and Kara's paper, the first solvable case they consider is the case of min-closed languages, and your problem happens to fall into this category. The algorithm they suggest is quite simple (in hindsight): look for a vertex $v_0$ which is never the target of any edge, and if you find one, ...


6

I think there is no simpler characterization than just the fact that the treewidth of $G$ is bounded. The intuition for why is that by subdividing each edge of a graph we get a bipartite graph with the same treewidth. In particular, we have a very simple reduction from determining the treewidth of a graph to determining the treewidth of a bipartite graph.


6

If $G$ is $2k$-regular, then a relaxed edge coloring with exactly $k$ colors is the same thing as a 2-factorization, and is known to always exist by results of Petersen 1891. Otherwise, let $k=\lceil\Delta/2\rceil$ where $\Delta$ is the maximum degree of $G$. Then obviously, at least $k$ colors are needed in any relaxed coloring of $G$. But $G$ can be ...


6

Theorem 1. For every $d$ and $k$, there is a graph with the desired properties. I'll describe the construction in two stages. First, construct a bipartite multi-graph $G_1=(L_1, R_1, E_1)$ where $L_1=\{\ell_1,\ell_2,\ldots,\ell_k\}$ $R_1 = \{r_1, r_2, \ldots, r_k\}$ $E_1$ is the multi-set union of $d-1$ matchings $M_1, M_2, \ldots, M_{d-1}$, where $M_h =...


5

It is known that a graph of treewidth $k$ and maximum degree $\Delta$ has tree partition width at most $O(k\Delta)$. See Wood, arXiv:math/0602507. From a tree partition of width $O(k\Delta)$ a triangulation of width $O(k\Delta)$ and maximum degree $O(k\Delta^2)$ follows pretty directly (start with the tree partition, make every bag into a clique, make every ...


5

A path has cliquewidth $3$, but the tensor product of two paths of length $n$ will contain a $\Omega(n) \times \Omega(n)$ size grid as an induced subgraph. And $n \times n$ grids are known to have cliquewidth $\Omega(n)$ (see “The rank-width of the square grid“ by Vít Jelínek)


5

This operation is called vertex elimination. See for example: "Triangulated Graphs and the Elimination Process", by Rose (1970). This type of operation is well-studied, among others, in the context of chordal graphs (see Wikipedia entry about perfect elimination orderings). A related problem of finding an optimal ordering for applying this ...


5

I think this problem has little to do with Cerny's conjecture. There the problem is to find a word that works for every pair of states. Here it is enough to show that the word will work whp. for any pair of states. An exponential lower bound on $f$ can be given as follows. Take a DFA whose states are $v_1,\ldots,v_k$ and the transition function is such that ...


4

I see this question only 2.5 years after, but I think I have a relevant answer. Indeed, it is at the core of the work we have done on Fast generation of random connected graphs with prescribed degrees. In this paper, we start with a connected graph, and perform large numbers of edge swaps in order to make it random. We however want to obtain a random ...


4

I emailed the author. He replied "yes that paper is wrong!". He has lost the passwords to remove it from the web.


4

Take a clique of size 5 and consider a graph on $n = 5k$ nodes consisting of $k$ copies of this clique. The size of a maximal cut in this graph is $6k = 6n/5$. Indeed, from each copy we can maximally have 6 edges in a cut. By the following lemma the size of a maximal cut can not be much smaller. Lemma. In any undirected 4-regular with $n$ nodes there exists ...


4

If you are happy with an approximation, then you can use approximate Laplacian solving, which takes time $\widetilde{O}(m)$. This is done explicitly in this paper by Spielman and Srivastava, Theorem 2. My guess is that this is optimal, even if you just want to determine the edge with maximal effective resistance.


4

In this answer i assume that $u$ is an ancestor of $v$ if $u$ can reach $v$ by a directed path. This is basically as hard as Set Cover (Given family $F$ over a universe $U$, find smallest subfamily $F’$ of $F$ whose union is $U$). To reduce from Set Cover: Make a vertex for every set in $F$ and for every element in $U$. Make an arc from every element to ...


4

For arbitrarily large number $n$ of variables, the following CNF formula $\phi$ is not satisfiable, has only three clauses, and a $2K_2$-free clause-variable incidence graph: $C_1=(x_1)$, $C_2=(\neg x_1)$, $C_3=(x_1,\ldots,x_n)$. Thus, to get more interesting lower bounds one needs to make assumption about the minimum clause size or about the size of classes ...


4

Let $G$ be a complete graph with $n$ vertices and $H$ be a complete graph with $n-1$ vertices, all marked. We replace each vertex of $G$ with $H$ to produce a graph $G^*$ with $n(n-1)$ vertices that is $n$-regular. We claim that the treewidth of $G^*$ is at least $n (n-1)/12$, which falsifies the conjecture. Proof: Suppose that the treewidth of $G^*$ is less ...


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 ...


4

I believe that this problem is NP-hard, here is a sketch proof (don't hesitate to ask for more details if needed). The idea is based on a reduction from the Not-all-equal 3-SAT. For $\varphi$ a 3-SAT formula with $m$ clauses, we will build $G(\varphi)$ a graph that has minimum objective value of $2\times m$ iif $\varphi$ has a solution. Before diving into ...


3

If I understood your statement correctly, then it is false: In a graph of maximum degree $3$ the $4$-connected components are all single vertices (and therefore planar AND of treewidth $\leq 1$). However we can make graphs of maximum degree 3 that contain arbitrarily large cliques as minors.


3

The problem is polynomial-time solvable. Observe that we have to pick exactly one vertex from each color class to form a $k$-clique. If there is a vertex $x \in V_{i}$ that has no neighbor in some $V_{j}$ with $i \ne j$, then no $k$-clique includes $x$. Thus, we can remove such a vertex. Repeat this until every vertex has a neighbor in each color class (...


3

When you make deductions in this coloring problem you are following paths in the dual graph to the triangulation. Any inconsistency could be described by a cycle in the dual graph (a cycle of triangles linked edge-to-edge in the given maximal planar graph) such that, when you color one of the triangles (it doesn't matter which one or which coloring) and then ...


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