11

An independent set that disconnects its graph is called an "independent cut", graphs that contain an independent cut are called "fragile graphs", and recognizing fragile graphs is known NP-complete [C. deFigueiredo, S. Klein, "NP-completeness of multipartite cutset testing", Congr. Numer. 119 (1996) 217–222, as cited by Guantao ...


7

Update: Sadly, it seems that my initial idea (see below) was incorrect, but it led to some fruitful discussion in the comments. As a result, the question is still open. Please let me know if you have any ideas. :) Initial Idea: One way to solve Triangle Finding is to find all pairs of vertices that are connected by a path of length 2. Then, you check if ...


6

There are old results showing that linear minor testing is possible for some specific graphs H, basically by looking at back-edge patterns in depth-first search, with significant effort for each H, and only a few are known. But, it is kind of like having linear FPT for k up to 4, which can make one suspicious. Recently discussed this issue with Rod. My own ...


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


6

I don't know of such a page. Most researchers have specific problems that they are interested in working on, and would only want to collaborate on those. If you pick a particular area and focus on developing your expertise and interests in that area, you could potentially reach out to individual researchers working on the same problems as you. For example, I ...


6

You can in cubic time figure out which pair of edges to let cross. For this, try all $O(n^2)$ pairs, augment the graph by replacing the two edges by a degree 4 vertex (representing the crossing), and test for planarity in linear time. If you already know the two edges that cross, you can use standard techniques to draw the augmented (planar) graph with ...


6

Update: Davide showed that this problem is PSPACE-hard here, settling PSPACE-completeness. NP-hardness This is NP-hard by reduction from 3SAT. Let's consider a formula in $k$ variables. Below is the construction for the formula $(x_1\lor x_2\lor x_3)\land(x_1\lor \neg x_2\lor x_3)\land(\neg x_1\lor x_2\lor \neg x_4)$ with $k=4$. I have drawn only the ...


6

As suggested by the comments (thanks!), the answer is positive and rather easy. We want to compute the pagerank of all vertices of a DAG (Directed Acyclic Graph) $G = (V,E)$ with $n$ vertices and $m$ edges. For any vertex $u$, let us denote by $d^+(u)$ its out-degree: $d^+(u) = |\{v, (u,v)\in E\}|$. Pagerank is basically defined as the stationnary ...


6

Found the following paper "NP-completeness of some problems of partitioning and covering in graphs" by B.Péroche. The paper proves that deciding whether the edges of a graph can be partitioned into two simple paths is NP-Complete. I haven't looked at the reduction but it may also prove that finding the min number of paths may be hard to approximate ...


5

No, this is impossible for your parameters. With $s$ bits of space, you can only visit at most $2^s$ vertices of the graph. Now set $s = O((\log k)^d)$ and $k=(\log n)^2$ and it is clear that you cannot visit all of the graph, as $2^s = o(n)$. Thus for any algorithm that uses only $O((\log k)^d)$ bits of space, there exist graphs where you fail to detect ...


5

PSPACE-completeness As suggested by Tim here, the problem can be shown to be PSPACE-hard by reduction from the Corridor Tiling Problem: Instance: a finite set of Wang tiles $\mathcal{T}=\{T_1,\ldots,T_h\}$, a special Wang tile $T_0$, and a width $n\in\mathbb{N}$ given in unary notation. Question: is there any height $m\in\mathbb{N}$ such that an $n\times m$ ...


5

Yes, there are many such algorithms. Two of the easiest are (1) Use Borůvka's algorithm, where each vertex finds its minimum-weight outgoing edge, you form trees from selected edges, collapse each tree to a supervertex, and repeat. But modify it so that after the collapse you return to a simple graph rather than a multigraph. To do so, use radix sort to sort ...


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

We answer OP's last question: can an approximate solution to IQP be obtained by randomized rounding? We show that the natural randomized-rounding scheme gives a 2-approximation, and a $(1+1/\overline d)$-approximation in graphs with average degree $\overline d$. (Note that any connected graph has average degree at least $2-2/|V|$.) For the record, here's the ...


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


4

Even computing a maximum independent set of unit axis-parallel squares is known to be np-hard: https://www.sciencedirect.com/science/article/pii/0020019081901113?via%3Dihub Since coloring is a "harder" problem, it should also be NP-hard. A constant approximation follows as if a point is covered by $k$ squares, then the chromatic number is at least $...


4

Per the section quoted in the comments, it appears that one of the cited documents takes input in the form of an adjacency matrix. In this scenario, taking $s$ and $t$ to correspond to the first and last indices respectively, we can prove that $\Omega(n^2)$ bits of the matrix may need to be read to decide STCONN even under the promise that the $(n/2)\times(n/...


4

I think you can extend Vinicius dos Santos' idea to show that no polynomial bound is possible. Consider a graph on $n$ vertices divided into $d\geq 1$ groups of size about $n/d$ as follows: Its transitive closure has about $(\frac{n}{d})^d$ maximal (undirected) cliques.


4

As TSP is an optimization problem, there are not many variants of it (that I know of) that add hard constraints to the formulation. But if I have understood correctly, your problem is a special case of (a variant of) the Prize-Collecting Travelling Salesman Problem (PCTSP), which seems to be introduced in [1] (NB: Technical report, written on typewriter. ...


4

Here's a counter-example for $k= 4$. Take $G = K_{2,2}$, specifically $G=(V, E)$ where $V=\{1,2,3,4\}$ and $E=\{(1,3), (1, 4), (2,3), (2,4)\}$. Define $b^1$ by $b^1_1 = b^1_3 = 1$ and $b^1_2=b^1_4=0$. Define $b^2 = b^1$. Define $b^3$ by $b^1_1 = b^1_3 = 0$ and $b^1_2=b^1_4=1$. Define $b^4 = b^3$. Then there is just one $b^1$ matching (which is also the only $...


3

You can reduce Boolean matrix multiplication (BMM) to this problem. (BMM is matrix multiplication over the OR/AND semiring with 0 and 1.) Imagine adding one more column to the first matrix A and one more row to the first matrix B, both of which are all-ones. If the BMM of A and B had a 0 in an entry, your new product over the integers will have 1, and if the ...


3

Definition: Given an undirected graph $G$ and an edge orientation $\vec{G}$, an unstable path is a directed path that goes from a node $s$ to a node $t$, such that the out-degree of node $s$ is strictly larger than the out-degree of node $t$ plus one. We observe that flipping the orientation of all edges along that path decreases the cost. Unstable path ...


3

It's a good question. You can use a Laplacian solver if $A$ is symmetric and diagonally semi-dominant (SDD). This is the subject of Theorem 9.2 in your reference book from Vishnoi. A good exposition of the proof (which was originally by Gremban) can be found in Appendix A of the paper by Kelner, Orecchia, Sidford and Zhu (arXiv:1301.6628). A recent result by ...


3

The statement of Ahuja, Magnanti, and Orlin applies to general flows, not only $(s,t)$-flows. During decomposition, when removing a path flow, either one of the two endpoints become balanced or one the arcs will get flow 0. This gives the bound $m+n$. In the case of $(s,t)$-flows, we may note that during decomposition the nodes $s$ and $t$ becomes balanced ...


3

(Copied from a comment:) If you are not interested in approximations, then you can equally well look at the question of maximizing the number of edges between different parts, and this is usually known as "maximum k-cut" and also "maximum k-colorable subgraph".


3

This paper by Régis Barbanchon might be of interest. From the abstract: We prove that the Satisfiability (resp. planar Satisfiability) problem is parsimoniously P-time reducible to the 3-Colorability (resp. Planar 3-Colorability) problem, that means that the exact number of solutions is preserved by the reduction, provided that 3-colorings are counted ...


3

This question was posted more than 8 years ago, and much progress was done since then. However, many questions remain open, even very natural ones like sampling a random graph with prescribed clustering coefficient. Also, sampling simple graphs (no loop, no multi-edge) with prescribed degree sequence made much progress but remains difficult. I would like to ...


3

To answer my own question, I have found that this problem is indeed NP-Hard via a reduction from the Cactus Augmentation Problem (which is NP-hard). In "Parameterized Algorithms to Preserve Connectivity" they show that a Cactus Augmentation Problem can be transformed into an equivalent Node-weighted Steiner Tree problem where each Steiner node is ...


3

These are not directly comparable: Goemans–Williamson and related work: find a cut in any graph G [of some graph family] that is at least X times the size of the maximum cut of G. This is the usual approximation ratio. The paper mentioned in the question and related work: find a cut in any graph G [of some graph family] that contains at least X fraction of ...


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