Return to Question

(This question is a bit of a "survey".)

I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some structural properties. The problem "feels" quite hard, and I fully expect it to be $\mathcal{NP}$-complete.For some reason I'm having a hard time even finding similar problems in literature.

An example of a problem that I would consider comparable to the one I'm dealing with:

Given a weighted tournament $G = (V,E,w)$, is there a feedback arc set in $G$ the edges of which fulfill the triangle inequality?

Note the difference to the traditional feedback arc set problem: I don't care about the size of the set, but I do care whether the set itself has a certain structural property.

Have you encountered any decision problems that feel similar to this? Do you remember whether they were $\mathcal{NP}$-complete or in $\mathcal{P}$? Any and all help appreciated.

(This question is a bit of a "survey".)

I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some structural properties. The problem "feels" quite hard, and I fully expect it to be $\mathcal{NP}$-complete. For some reason I'm having a hard time even finding similar problems in literature.

An example of a problem that I would consider comparable to the one I'm dealing with:

Given a weighted tournament $G = (V,E,w)$, is there a feedback arc set in $G$ the edges of which fulfill the triangle inequality?

Note the difference to the traditional feedback arc set (DFAS) problem: I don't care about the size of the set, but I do care whether the set itself has a certain structural property.

Have you encountered any decision problems that feel similar to this? Do you remember whether they were $\mathcal{NP}$-complete or in $\mathcal{P}$? Any and all help appreciated.

(This question is a bit of a "survey".)

I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some structural properties. The problem "feels" quite hard, and I fully expect it to be $\mathcal{NP}$-complete.For some reason I'm having a hard time even finding similar problems in literature.

An example of a problem that I would consider comparable to the one I'm dealing with:

Given a weighted tournament $G = (E,V,w)$, is there a feedback arc set in $G$ the edges of which fulfill the triangle inequality?

Note the difference to the traditional feedback arc set problem: I don't care about the size of the set, but I do care whether the set itself has a certain structural property.

Have you encountered any decision problems that feel similar to this? Do you remember whether they were $\mathcal{NP}$-complete or in $\mathcal{P}$? Any and all help appreciated.

(This question is a bit of a "survey".)

I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some structural properties. The problem "feels" quite hard, and I fully expect it to be $\mathcal{NP}$-complete.For some reason I'm having a hard time even finding similar problems in literature.

An example of a problem that I would consider comparable to the one I'm dealing with:

Given a weighted tournament $G = (V,E,w)$, is there a feedback arc set in $G$ the edges of which fulfill the triangle inequality?

Note the difference to the traditional feedback arc set problem: I don't care about the size of the set, but I do care whether the set itself has a certain structural property.

Have you encountered any decision problems that feel similar to this? Do you remember whether they were $\mathcal{NP}$-complete or in $\mathcal{P}$? Any and all help appreciated.