4 votes

property of minimal triangulations

As @Laakeri commented, the connection between triangulations and minimal separators can be used to show this property. Based on the definitions: A subset $S \subseteq V$ is an $a, b$-separator of $G$ ...
Marko Lalovic's user avatar
4 votes
Accepted

Polynomial time algorihtms for two variants of the decision version of longest walk problem

I deleted my previous answer because there were some inaccuracies. Also I am going to assume that either, you are looking for the longest walk, with any nodes as endpoints, or you are looking for a ...
NaturalLogZ's user avatar
4 votes
Accepted

Maximum cardinality matching on DAGs

A matching that lies on a path of length (number of edges) $m$ has at most $m+1$ vertices, and therefore at most $\lceil m/2\rceil$ edges; conversely, such a path does include a matching with $\lceil ...
Emil Jeřábek's user avatar
4 votes
Accepted

Independent set queries with preprocessing

If the graph is uniformly sparse in the sense that every subgraph with $n$ vertices contains at most $d \cdot n$ edges for some small $d$, then degeneracy ordering could be exploited to have $O(|E|)$ ...
Laakeri's user avatar
  • 1,766
4 votes

Minimum number of triangles required to cover a complete graph?

This problem is the subject of (and was completely solved in) the paper "M. K. Fort Jr. and G. A. Hedlund. Minimal coverings of pairs by triples. Pacific Journal of Mathematics, 8(4):709–719, ...
Nathaniel Johnston's user avatar
3 votes
Accepted

What is the treewidth of the 3D-grid (mesh or lattice) with sidelength n?

It is $\Theta(n^2)$. The argument to prove the lower bound is that we can send an all-pairs concurrent flow of value $1$ and congestion $O(n^4)$, i.e., we can simultaneously send one unit of flow ...
Laakeri's user avatar
  • 1,766
3 votes

Can Lexicographic BFS be implemented in logspace?

It is not clear that the OP meant lexicographic BFS. The OP let (paraphrasing) $u_1$ be $v_1$, and the next elements $u_2$, $u_3$, etc., of the output, be the neighbors of $v_1$ according to the input ...
Siddharth's user avatar
  • 841
2 votes

Transitive reduction not provably minimal

The proposed algorithm won't reliably deliver a minimal result because it does nothing to eliminate redundant edges between connected components. The simplest illustration of this is this acyclic ...
Mark Amery's user avatar
2 votes
Accepted

Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes

There is no poly-time approximation algorithm for this problem unless P=NP. For the metric case (when the graph is complete and the edge weights satisfy the triangle inequality), there is a poly-time ...
Neal Young's user avatar
  • 10.8k
2 votes

What is the fastest algorithm for computing exact network reliability?

This paper shows an exact mapping from reliability to exact model counting. From that point on, exact counters (like miniC2D) can be used to compute reliability. Not sure if useful runtime bounds ...
delete000's user avatar
  • 818
1 vote
Accepted

Shorter than target vector path algorithm

The problem is NP-hard, even in just two dimension, by reduction from the knapsack problem. Consider a 0-1 knapsack instance with $n$ items, where the weight of the $i$th item is $w_i$ and its value ...
D.W.'s user avatar
  • 12.1k
1 vote

Question about claw-free graphs

Consider the graph $G = (V,E)$ with vertex set $V=\{a,b,c,d,x,y,z,u\}$ and edge set $E=\{ac,bd,au,bu,cu,du,ax,bx,cy,dz\}$. Then, if I am not mistaken, $x,b,u,c,y$ is an induced path through $u$ ...
NaturalLogZ's user avatar
1 vote

Given a weighted graph with $pk$ nodes find a min weight forest with $p$ components each containing exactly $k$ nodes

I think I can show that the problem is NP-hard, even in the case where the graph is unweighted. Specifically, given an undirected graph $G$, and values $p$ and $k$, I want to know if I can partition ...
a3nm's user avatar
  • 9,269
1 vote
Accepted

Counting the different subsets of nodes seen when iterating a subset through a directed graph

The argument in Chrobak’s paper can be applied to this problem as well, with the same bounds. Let $\{D_i:i<k\}$ be the set of strongly connected components of $G$ that contain a cycle (i.e., other ...
Emil Jeřábek's user avatar
1 vote

A variation of the longest path problem

What are you wondering about this problem? If $X$ is an input, it is obviously at least as hard as the longest path problem, since it contains the longest path problem as a special case ($X=1$). But I ...
NaturalLogZ's user avatar
1 vote

Bottom up TSP solution?

"If one takes the 2 nearest neighbors of every node and adds them all up, that is a theoretical minimum." This isn't true. You are adding up 2 edges per vertex, where a TSP solution has one ...
NaturalLogZ's user avatar
1 vote

Efficient Algorithm for Partitioning a Directed Acyclic Graph into Short Paths

Claim: There exists an almost linear time approximation algorithm that returns $m$ paths such that $m \leq (2-\frac{1}{k})OPT$ respecting the length conditions. Since you say $k < 20$, this should ...
user3508551's user avatar
  • 1,153
1 vote
Accepted

What is known about the complexity of Network Diversion?

We have a recent preprint where we show it's polynomial-time on planar graphs: https://arxiv.org/abs/2305.01314. In general graphs, it remains open whether it is polynomial-time or NP-complete. An FPT ...
Laakeri's user avatar
  • 1,766
1 vote

What's the exact complexity of a DFS if we revisit nodes?

Suppose the graph has an adjacency matrix $M$. It's well known that the number of paths of length $k$ from $i$ to $j$ is $(M^k)_{ij}$. Since we care about paths of any length, we are interested in $M^...
Command Master's user avatar
1 vote

Approximative counting of matchings in a graph

Both Jerrum and Sinclair have written a lot about this kind of topic over the years, and there are more recent references by them that you can check out. In particular, take a look at [1], it ...
acrendic's user avatar
1 vote

Upper Bound for distance-two chromatic number in terms of maximum degree

Let $\Delta$ denote the maximum degree of $G$. The bound $\Delta^2+1$ cannot be improved significantly. For instance, even for a colouring variant called 2-ranking (which is a generalisation of ...
Cyriac Antony's user avatar
1 vote
Accepted

A non-trivial combinatorial optimization

This is NP-hard even for $d=1$ by reduction from the (strongly NP-hard) Product Partition problem. Lemma 1. The problem (with either objective function) is NP-hard, even for $d=1$. Proof sketch. Given ...
Neal Young's user avatar
  • 10.8k
1 vote

Generate TSP instances with known optimal

If someone is still searching for this, I might give a gist of how I understood that paper: Generate an optimal permutation $p$ of $\{1...n\}$. Create two random variables, $\alpha_i$ and $\beta_j$, ...
Ferazhu's user avatar
  • 11
1 vote

Maximal classes for which largest independent set can be found in polynomial time?

In the meantime, it was shown that the problem is polynomial-time solvable on $P_6$-free graphs: Andrzej Grzesik, Tereza Klimosová, Marcin Pilipczuk, Michal Pilipczuk: Polynomial-time Algorithm for ...
Christian Komusiewicz's user avatar

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