How to look for the edges that must exist in every minimum spanning trees of a weighted graph

Given an undirected weighted graph, the actual weights of the edges are not known, however; instead, each edge is classified as either Light, Medium or Heavy.

All Light edges have a smaller weight than any Medium or Heavy edge.

All Medium edges have a smaller weight than any Heavy edge

In general, nothing is known about the relationship between two edges in the same weight class. Then, how to identify all the edges that must exist in every MST of this graph? The following is what I’m thinking:

  1. determine the number of strongly connected components.
  2. the edges composed of articulation points must exist in the MST.
  3. The lightest edge in each connected component must exist in the MST.

I am not sure whether my thinking is correct or not? If it is correct, how to implement the code with java? Thank you very much.

Find all critical edges for minimum spanning tree

This is a problem from the textbook “Algorithms, 4th edition” by Robert Sedgewick and Kevin Wayne.

4.3.26 Critical edges. An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. Show how to find all critical edges in a graph in time proportional to $E log E$. Note: This question assumes that edge weights are not necessarily distinct (otherwise all edges in the MST are critical).

There is an algorithm (see below), as well as an accepted answer, at stackoverflow.
However, in my opinion, the correctness proof is not complete because it does not justify that all critical edges can be found. Moreover, I cannot figure out how the time complexity of $O(m log m)$ is achieved in this algorithm (given the hint in the answer).

The algorithm is (in my understanding):

  • Run Kruskal algorithm on this graph. Whenever we encounter an edge $e$ whose insertion in the MST creates a cycle, the edges in this cycle with smaller weights than $w(e)$ will be reported as critical edges.

My questions are:

  • How to prove the correctness of this algorithm: (1) all edges reported are critical edges; (2) all critical edges are reported?
  • How to achieve $O(m log m)$ with appropriate data structures?
  • If this algorithm is wrong, how to solve the problem?

How to restore a broken minimal spanning tree?

We’re given $T$ a minimal spanning tree (MST) of a non-directed, connected graph $G=(V,E)$ with non-negative weights for each edge $e in E$. Let $e^* in T$ be an edge in $T$ and let $G’=(V,E’)$ be the graph which we get after removing $e^*$ ($E’=Esetminus {e^*}$). $G’$ is also connected.

I need to propose an algorithm which will run in $O(|E|)$ time and will restore $T$ such that it will yield an MST $T’$ for $G’$.

I’m really not sure if I’m in the right direction but this is what I thought of:

Let $e^*=(u,v)$.

a) We mark $e^*$ and remove it from $T$ and b) find the connected component of node $v$ by using BFS algorithm on $T$.

Now we have 2 connected components:

  1. the first starts from $v$ let’s call it $S = Tsetminus e^*$
  2. the second is $Vsetminus S$

Clearly $e^*notin S$ and $e^* notin Vsetminus S$. Also $Sneq V$ because otherwise we’d get a connected graph after the removal of $e^*$ of $n-1$ edges which would mean that there were $n$ edges in $T$ which is a contradiction since $T$ is a tree.

c) Then we start looking for a minimal edge $e’$ from $uin Vsetminus S$ to $vin S$.

d) Once we found $e’$ we’ll add it to $T$ and we’ll get $T’$.

I’m having trouble with running times.

a) we need to traverse $G$ in order to find $e^*$ so it’s the running time of BFS which is $O(|E|+|V|)$ and because $G$ is connected ($|E| ge |V|-1$) then the time is $O(|E|)$.

b) BFS again so $O(|E|)$.

c) This could also be $O(|E|)$ because in the worst case the graph could be something like this:
G

d) is O(1).

Column based layout with cell spanning multi pages

I want create a layout which looks like this (porting a document from Word to LaTeX):

Multi column layout - Word

I tried to use a table to implement this, but the problem is that the text for ‘Attr6’ can span multiple pages.
As far as I understand this is not possible with tables, even with longtable .

Another approach was to use multicols:

begin{mutlicols}{2}
    Attr6: columnbreak
    Value6
end{multicols}

But the problem with this solutions is that a muli-page text looks like:

Attr6:                 Value6
                       ...more text
------  ------------

...text continued
on the left column...

What else can I use to create this 2 column layout ?

How to prove that $3$-Spanning-Tree decision problem is $NP$-Complete

I am not sure what problem may reduce to $3$SpanningTree where $3$SpanningTree is defined as a decision problem which given an undirected graph $G$ determines if there is a spanning tree of $G$ in which every vertex has degree no larger than $3$.

I have already done this for $2$SpanningTree using a reduction from Hamiltonian paths as this reduction seemed clear. A spanning tree where each node has degree at most $2$ is essentially a Hamiltonian path in the given graph.

I am not sure if I can extend this idea to $3$SpanningTree or need to try a different approach entirely, any help would be welcome.

Special minimum spanning tree

There is a node that can only get one line, I use both kruskal and prim, but the judger said TLE(Time Limit Exceed).
Then I will describe the question. There are many computers, we need to connect all of them, we give the cost of connection between different computers, also we give the special number of computer which can be only connected by one line. Finally, we guarantee there is a answer and there is no Self-Loop, but there may have multiple edge which have different weight between same node.
Here is my kruskal code, it’s TLE.

#include 
#include 

using namespace std;

typedef struct edge{
    int start;
    int end;
    int weight;
}Edge;

int special = 0;
int edgenum;
Edge _edge[600005];
int i, j, k;
int counter = 0;

bool Cmp(const edge &a, const edge &b){
    return a.weight < b.weight;
}

int getEnd(int vends[], int i){
    while(vends[i] != 0)
        i = vends[i];
    return i;
}

void kruskal(){
    int p1, p2, m, n, ans = 0;
    int vends[10005] = {0};
    sort(_edge, _edge+counter, Cmp);
    for(i = 0; i < edgenum; ++i){
        p1 = _edge[i].start;
        p2 = _edge[i].end;
        if ((p1 == k || p2 == k) && special)
            continue;

        m = getEnd(vends, p1);
        n = getEnd(vends, p2);

        if(m != n){
            if (p1 == k || p2 == k)
                special = 1;
            vends[m] = n;
            ans += _edge[i].weight;
        }
    }
    cout << ans << endl;
}

int main(){
    int n, m;
    cin >> n >> m >> k;
    edgenum = m;
    while(m--){
        int a, b, c;
        cin >> a >> b >> c;
        _edge[counter].start = a;   //Get the Edge
        _edge[counter].weight = c;
        _edge[counter++].end = b;
//        _edge[counter].start = b;
//        _edge[counter].weight = c;
//        _edge[counter++].end = a;
    }
    kruskal();
}

Here is my Prim, but also TLE:

#include 

using namespace std;

typedef char VertexType;

typedef struct node{
    int adjvex = 0;
    int weight = INT32_MAX;
    struct node *next = NULL;
}Node;

typedef struct vnode{
    VertexType data;
    Node *firstnode = NULL;
}Vnode;

Vnode node[10005];
int VNUM;
int n, m, k;
int lowcost[10005] = {0};
int addvnew[10005];  //未加入最小生成树表示为-1,加入则为0
int adjecent[10005] = {0};
bool is_special = false;
int flag;

void prim(int start){
    long long sumweight = 0;
    int i, j;
    Node *p = node[start].firstnode;

    for (i = 1; i <= VNUM; ++i) {   //重置
        addvnew[i] = -1;
    }

    while (p->next != NULL){
        if (lowcost[p->adjvex] == 0 || p->weight < lowcost[p->adjvex])
            lowcost[p->adjvex] = p->weight;
        p = p->next;
    }
    if (lowcost[p->adjvex] == 0 || p->weight < lowcost[p->adjvex])
        lowcost[p->adjvex] = p->weight;

    addvnew[start] = 0;
//    adjecent[start] = start;
    if (start == k) {
        is_special = true;
        flag = 1;
    }

    for (i = 1; i < VNUM; ++i) {
        int min = INT32_MAX;
        int v=-1;
        for (j = 1; j <= VNUM; ++j) {   //Find the min
            if (addvnew[j] == -1 && lowcost[j] < min && lowcost[j] != 0){
                min = lowcost[j];
                v = j;
            }
        }
        if (v != -1){   //if min is found
            if (flag == 1){
                for (int l = 0; l < 10005; ++l) {
                    lowcost[l] = 0;
                }
                flag = 0;
            }

            addvnew[v] = 0;

            sumweight += min;

            p = node[v].firstnode;
            while(p->next != NULL){
                if (is_special && p->adjvex == k){  //If find the special node
                    p = p->next;
                    continue;
                }
                if(addvnew[p->adjvex] == -1 && (lowcost[p->adjvex] == 0 || p->weight < lowcost[p->adjvex])){    //如果该点未连接
                    lowcost[p->adjvex] = p->weight;
                }
                p = p->next;
            }
            if (!(is_special && p->adjvex == k))
                if(addvnew[p->adjvex] == -1 && (lowcost[p->adjvex] == 0 || p->weight < lowcost[p->adjvex])){
                    lowcost[p->adjvex] = p->weight;
                }
        }
    }
    cout << sumweight << endl;
}

int main(){
    cin >> n >> m >> k;
    VNUM = n;
    while (m--){
        int a, b, c;
        cin >> a >> b >> c;
        Node *p = (Node*)malloc(sizeof(Node));
        p->adjvex = b;
        p->weight = c;
        p->next = node[a].firstnode;
        node[a].firstnode = p;
        Node *q = (Node*)malloc(sizeof(Node));
        q->adjvex = a;
        q->weight = c;
        q->next = node[b].firstnode;
        node[b].firstnode = q;
    }
    prim(k);
}

I don’t know how to modify the both code, I try my best, thank you

show that a loopless graph $G$ contains a bipartite spanning subgraph $H$ such that $d_H(v) ge frac{1}{2}…

The hint in the appendix of book says that bipartite subgraph with with largest possible number of edges has such a property, but I don’t know how to use this hint!

any help would be appreciated.

Computational complexity of finding a spanning tree in planar hybergraphs

Using a bipartite graph to represent hypergraphs as described by Wikipedia :

A hypergraph $H$ may be represented by a bipartite graph $BG$ as follows:
the sets $X$ and $E$ are the partitions of $BG$, and ($x_1$, $e_1$) are
connected with an edge if and only if vertex $x_1$ is contained in edge $e_1$
in H.
Conversely, any bipartite graph with fixed parts and no unconnected
nodes in the second part represents some hypergraph in the manner
described above. This bipartite graph is also called incidence graph.

Now if we assume that a hybergraph is planar if and only if it can be represented by a planar bipartite graph. What is the complexity of finding a spanning tree in planar hybergraphs? It is also ok if you can provide any source on how to approach this problem.


Note: It is known that the spanning tree problem of general hybergraphs is $NP$-complete, while spanning tree of $3$-uniform hypergraphs, where all hyperedges are of size $3$, has a polynomial algorithm using matroid matching [ref].

Note: Under the bipartite representation of hypergraphs the problem of spanning tree becomes equivalent to the problem of finding a subset of vertices that induces a tree such that the tree contains all vertices of one of the bipartitions of the bipartite graph. The problem is a bit similar to the Induced-Tree problem defined in this paper, but in this problem the induced tree must contain any set $S$ of vertices as part of the problem input. The Induced-Tree problem is $NP$-complete even for planar bipartite cubic graphs.

Spanning content within a tabbing environment across multiple pages

I’m trying to update a CV I wrote a long time ago based on the Wilson Resume template.

However, I’ve run into an issue in which the content I’ve added for a job listed in my career history is too long, and since it can’t break across pages the typesetter has put it all on a separate page:

What I’d like is it to just run the job details onto a new page if it gets too long without shifting the entire thing onto the new page. I haven’t worked with LaTeX in a while so I’m pretty rusty with it. The template I use defines the following command that I use to list each job:

newcommand{job}[6]{
begin{tabbing}
hspace{2cm} = kill
textbf{#1} > href{#4}{#3} \
textbf{#2} >+ textit{#5} \
begin{minipage}{smallertextwidth}
vspace{2mm}
#6
end{minipage}
end{tabbing}
vspace{2mm}
}

In this command, #6 is replaced by the long job description.

I’ve tried playing around with this command by e.g. trying to remove the minipage environment. However, almost anything I do to modify this command results in dozens of errors that I don’t understand. For example, I would expect the following to compile:

newcommand{job}[6]{
begin{tabbing}
hspace{2cm} = kill
textbf{#1} > href{#4}{#3} \
textbf{#2} >+ textit{#5} \
vspace{2mm}
#6
end{tabbing}
vspace{2mm}
}

When I run this through XeLaTeX, it produces the following errors:

Trying to move Tablet from spanning displays to one of two monitors

I have a Wacom Bamboo CTL-470.

I was attempting to force it onto a single monitor and I did the command

xinput map-to-output "Wacom Bamboo Connect Pen stylus" HDMI-3

and also tried

xinput map-to-output 15 DVI-1

my problem is that now my tablet does not appear to function at all but still shows up when I do xinput --list

xinput --list
⎡ Virtual core pointer                      id=2    [master pointer  (3)]
⎜   ↳ Virtual core XTEST pointer                id=4    [slave  pointer  (2)]
⎜   ↳ Gaming KB  Gaming KB                      id=12   [slave  pointer  (2)]
⎜   ↳ Corsair Corsair M65 Gaming Mouse          id=13   [slave  pointer  (2)]
⎜   ↳ Corsair Corsair M65 Gaming Mouse          id=15   [slave  pointer  (2)]
⎜   ↳ Wacom Bamboo Connect Pen eraser           id=10   [slave  pointer  (2)]
⎜   ↳ Wacom Bamboo Connect Pad pad              id=16   [slave  pointer  (2)]
⎜   ↳ Wacom Bamboo Connect Pen stylus           id=9    [slave  pointer  (2)]

How would you Guys recommend I move my tablet to a single monitor. Also any input on what I did wrong so that I can learn from my mistake would be handy.