Let $G=(V,E)$ be an unweighted directed acyclic graph with a set $V$ of vertices and a set $E$ of edges. The all-pairs shortest path problem can be solved efficiently using the Floyd-Warshall algorithm. The new objective is to find a subset of maximum cardinality $S \subseteq V$ such that for every pair of vertices $v$ and $u$ in $S$, the length of the shortest path from $v$ to $u$, if it exists, is greater than or equal to a positive natural number $k$. This problem could be stated as a bottleneck capacity maximization problem in a complete directed weighted graph. You are given a complete weighted directed network and the objective is to find an induced subgraph with $m$ vertices where the minimum arc capacity is greater than or equal to $k$. The reduction gives the arc from $v$ to $u$ a weight equal to the shortest path computed by Floyd-Warshall from $v$ to $u$ (if there is no path, a weight of $\infty$ is given). Is there an efficient/polynomial time dynamic programming approach to solve the problem?

I have a tree, $T$, with $n$ nodes. My goal is to assign a non-zero weight to each node such that the following condition is met: Upon removing any arbitrary node, the total weight of nodes in each resulting connected component should be equal. Consider the following tree as an example: ``` 1 -- 2 -- -3 -- 4 | 1 ``` In this tree, if we remove any node, the total weight of the nodes in each of the resulting connected components is equal. For instance, if we remove the node with weight $-3$, we end up with two connected components, each with a total weight of $4$. I am seeking an algorithm that can find these weights in polynomial time. My initial approach was to assign arbitrary values to the nodes. Then, for each node, I would check if the condition is satisfied when that node is removed. This check can be performed in $O(n)$ time using graph traversal algorithms like BFS or DFS. However, I am unsure how to adjust the tree because correcting the condition for one node seems to disrupt the condition for almost all other nodes. Any suggestions or insights would be greatly appreciated.

Given an undirected graph $G$ and two vertices $s$ and $t$, i want to find a minimum set of edges $E$ in $G$ such that every (simple) $s$-$t$-path contains at least 2 edges from $E$. Is this problem solvable in polynomial time? What if the paths should not contain 2, but $r$ edges in $E$? I know that for $r=1$, this is equivalent to simply finding a minimum $s$-$t$-cut, so maybe the problem can be solved by using MaxFlowMinCut-techniques?

How can we prove that for $\\\\$ every $\\\\$ 2-connected graph G with an odd number of vertices, the unsatisfiable Tseitin formula for it is minimally unsatisfiable, that is, if we remove even a single clause, it becomes satisfiable?

Is the following adaptation of the graph bandwidth problem NP hard? If so, which problem could a reduction use? Given: Graph $G = (V , E ), L:E\to \mathbb N$. Question: Is there a $f : V \to \mathbb Z$ where for each $e = \{u, v \} \in E$, $|f (u) - f (v )| = L(e)$?

The 2-coloring problem is in P. How can I prove that it is in NL or L? I see that I should create a deterministic/nondeterministic algorithm with logarithmic space, but I have no idea how to store the coloring in logarithmic space.

In the wikipedia page for the NP-intermediate complexity class, the following observation is made: Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, although this problem is artificial and otherwise uninteresting. It is an open question whether any "natural" problem has the same property [...] In the '80s, a work by Galperin and Widgerson was dedicated to problems on graphs with succinct circuit representations. Intuitively, a graph has a succint circuit representation if there is a polylogarithmically sized boolean circuit which takes two (padded) integers representing node numbers as input, and outputs 1 if there is an edge between those two nodes and 0 otherwise. Many NP-complete predicates of graphs were shown to be NEXP-complete when the graph is provided in its succinct form. Now consider any particular NP-complete problem among these. The above fact can be because, aside from the input having become exponentially smaller, the following informal statement must be true: Call $\sigma$ the subset of instances of the original NP-complete problem that are representable by a succinct circuit. $\sigma$ turns out to not be dramatically easier to decide than its parent set; that is, $\sigma$ is not susceptible to some specialized, polynomial method leveraging some particular structural peculiarity common to all its members. In fact, if there was a polynomial time algorithm A that, when applied to members of $\sigma$ (it doesn't even matter what A does with the other instances!), would correctly decide them, you could simply "decompress" the graph and then use A to decide the instance. Both of these steps take deterministic time exponential in the succinct input length. But the succinct problem is NEXP complete, so this could happen only if EXP=NEXP. This provides evidence that $\sigma$ itself is not in P unless EXP=NEXP. To decide $\sigma$, you would need to establish that the instance has a small circuit, then solve it. The first pa

In the context of finite, simple, undirected graphs, associate with each node $v\in V$ an integer $n(v)$ (you can limit this to positive integers without loss of generality). Create the set of edges by defining a threshold $T$, and join an edge $x,y$ iff $n(x)+n(y) \geq T$. These are called threshold graphs$^{[1]}$ and they are well-studied, their structure has been characterized. If, instead, $x,y$ are joined by an edge iff $n(x)+n(y)=0\ (mod\ T)$, we form another very simple class of graphs. But have they been studied and do they have a name? $^{[1]}$ Chvátal, Václav; Hammer, Peter L. (1977), "Aggregation of inequalities in integer programming", in Hammer, P. L.; Johnson, E. L.; Korte, B. H.; et al. (eds.), Studies in Integer Programming (Proc. Worksh. Bonn 1975), Annals of Discrete Mathematics, vol. 1, Amsterdam: North-Holland, pp. 145–162.

$\mathrm{MFVS} \leq 1$ is a concise way of writing the following decision problem: Let $G = (V, E)$ be a directed graph. Is there a $v \in V$ such that every cycle in $G$ passes through $v$? (More generally, $\mathrm{MFVS}$ stands for minimal feedback vertex set, the problem of finding the smallest set of vertices such that every cycle passes through at least one of them. In general, MFVS is NP-complete.) There is a trivial $\mathcal O(VE)$ algorithm: for every vertex $v$, use a $\mathcal O(E)$ cycle-finding algorithm, like a topological sort, to check if there is a cycle in $G$ that does not pass through $v$. I am wondering if we can do better: is it possible to solve this problem, either deterministically or probabilistically, in $\mathcal O(E^{2 - \epsilon})$, or even (ideally) in $\mathcal O(E)$? There is a simple algorithm that seems promising: start with a set of candidate vertices $X = V$, and then alternate between: - picking a $v \in X$ and testing if it forms a feedback vertex set by itself; if not, remove it from $X$; - finding a random cycle in $G$, and removing all vertices from $X$ that are not on that cycle. Unfortunately, it is possible for there to be a large set of vertices so that the vast majority of cycles contain the vast majority of those vertices, even if the answer to the decision problem is negative. So there is a class of graphs on which the above turns into a quadratic algorithm (with high probability) after all.

I would like to know if there is any research dealing with the problem of constructing an increasing family of expander graphs. The goal is to find a family of expander graphs $(G_i)_{i \in \mathbb{N}} = ((V_i,E_i ))_{i \in \mathbb{N}} $ satisfying $V_1 \subseteq V_2 \ldots \subseteq V_n$ and $E_1 \subseteq E_2 \ldots \subseteq E_n$ for all $n \in \mathbb{N}$ and more idealy a family where $V_i = \{1,2 \ldots, n \}$.