Andrew D. King
  • Member for 11 years, 1 month
  • Last seen more than a month ago
20 answers
50 votes
8k views
NP-hard problems on trees
14 votes

The firefighter problem has received a fair amount of attention recently, and is (somewhat surprisingly) NP-hard on trees of maximum degree 3. It is actually a fairly natural question, described as ...

View answer
2 answers
5 votes
5k views
Any relation between the size of maximum independent set and the chromatic number on graph of bounded degree?
Accepted answer
11 votes

Obviously if $f(\Delta)=2\Delta$ then the bound holds. However, I doubt this is what you meant. Perhaps you meant $\chi(G) \leq f(\frac n k)$, in which case the answer is no, there is no such ...

View answer
17 answers
38 votes
4k views
Conjectures implying Four Color Theorem
11 votes

Every bridgeless cubic planar graph is 3-edge-colourable. (This is equivalent to 4CT, due to Tait.)

View answer
6 answers
4 votes
776 views
Is feedback vertex set problem is solvable in polynomial time for some special graph
10 votes

Surely the problem is polytime for graphs of bounded treewidth via dynamic programming.

View answer
1 answers
16 votes
258 views
Is it enough to sort for polynomially many 0-1 sequences for a sorting network?
Accepted answer
8 votes

It seems not. Ian Parberry makes reference to a paper by Chung and Ravikumar, where they supposedly give a recursive construction of a sorting network that sorts every bitstring but one, and further ...

View answer
1 answers
6 votes
323 views
Decomposition by Clique Separators
Accepted answer
6 votes

Chvátal and Sbihi (Recognizing Claw-free Perfect Graphs, JCTB 44) described the atoms for the class of claw-free perfect graphs, a.k.a. quasi-line perfect graphs. This description was later refined ...

View answer
1 answers
7 votes
375 views
Finding balanced disjoint cycles in bridgeless cubic graphs
Accepted answer
5 votes

This is NP-complete; reduction from the question, "Does a 2-edge-connected cubic graph $H$ contain a Hamiltonian cycle avoiding a given edge $e$?" Construct $G$ as follows. Take two copies of $H-e$, ...

View answer
1 answers
3 votes
128 views
How to find the first $k$ points of high enough level using a priority search tree?
Accepted answer
5 votes

The tree is binary and has depth $O(\log(n))$ and the properties that: for any non-root node $v$, the y-coordinate of $v$ is larger than that of its parent. for any node $v$, all descendants in the ...

View answer
2 answers
12 votes
544 views
Approximate graph colouring with a promised upper bound on maximum independent set
5 votes

You might be interested in the colouring number, which is 1 plus the maximum over all subgraphs $H$, of the minimum degree of $H$. It can be computed efficiently, and is an upper bound for the ...

View answer
1 answers
4 votes
162 views
Given a network flow, are there bounds on the change in weight on nodes?
Accepted answer
4 votes

I think you're using a confusing sign convention, but I'll stick with it. It's pretty easy to see that for any connected graph you can have all weight flowing into a single vertex (unless I'm ...

View answer
1 answers
7 votes
426 views
Combinatorial Independent set Algorithms for sub-classes of perfect graphs
Accepted answer
4 votes

One springs to mind and is listed as a maximal subclass in ISGCI, which surprised me: perfect claw-free graphs (a.k.a. perfect quasi-line graphs). This was done by Minty for all claw-free graphs ...

View answer
2 answers
24 votes
911 views
Is there a direct/natural reduction to count non-bipartite perfect matchings using the permanent?
4 votes

This is obviously a comment and not an answer, but I don't have any reputation points here yet, so sorry about that. For non-bipartite cubic bridgeless graphs, there are exponentially many perfect ...

View answer
1 answers
3 votes
938 views
Max-cut equivalence with most likely assignment to an Ising model
Accepted answer
3 votes

Finding the most likely assignment in the Ising model is equivalent to maximum cut, so forget about minimum cut for a minute. In the formulation you give for the Ising model, we are trying to ...

View answer
3 answers
4 votes
3k views
Maximum-clique practical applications
2 votes

Finding a maximum (or at least large) clique is often useful because it gives you a lower bound on the fractional chromatic number and chromatic number of the graph in question. Actually the maximum ...

View answer
2 answers
12 votes
891 views
Minimum maximal solutions of LPs
2 votes

You may find it useful to look into blocking and anti-blocking pairs of polyhedra. Say you have a packing problem. Then your feasible region $P$ is a corner polyhedron in the nonnegative orthant, ...

View answer
3 answers
1 votes
2k views
Sorting array of distances by proximity to each other
1 votes

It might be useful to store the data in a graph of nodes corresponding to the Delaunay Triangulation of the geometric data points. Then if you wanted to query an area you could do so by starting with ...

View answer