You know, I was thinking about the problem a little differently, but came to a similar conclusion.
Start with essentially the same premise as Ginkapo. Konstantine's value is in splitting the enemy force, but he has to have medium ships in at least long range to do so. That means you're eating reds from the part of the fleet that you "split off", which wouldn't be too big a deal, except every med+ Imperial ship has no (native) evade. So you need to find a way to split the force in such a way that your primarily-threatened ships have evades, but you don't have medium+ ships that can do that. Which means you might prefer that your fleet be split between two categories of ship. I was thinking of them as:
"Triggers"--a pair of fast, fairly agile medium ships to set off Konstantine. Ideally, these would have evades, so you could drop Needa on one and activate the other early to try and minimize the number of ranged shots it eats.
"Exploiters"--something with evades to weather the long-range fire and make splitting the fleet worthwhile, but also limited threat range to maximize your points efficiency (that is, you're not paying for reds you're not planning to use). Alternatively, these might take the form of a strong long-range platform that can sit far enough behind the kill-zone as to not be eating shots from the "split" part of the fleet and can focus down the "prey". This variant would not need to be evade-centric, but would need to put through strong, efficient long range fire.
There aren't a lot of options for triggers--it's pretty much a QF, an ISD, or an Interdictor+ET. Speed 2 is just too slow to get out into and back out of the flanking positions you'd need to set up to catch and then avoid the bulk of the enemy fleet. QF is the most cost-effective option, but doesn't bring a lot to the long-range fight, and only has a single brace/redirect to replace with a Needa evade. Interdictor+ET can bring a lot to the overall fight in addition to the trigger role, but isn't cheap and thus starts to eat into your exploiter budget. The ISD is a fantastic platform, but ends up kind of having to perform double duty if you're going to go that direction.
The exploiters is an easier problem. The role can be filled by Raiders or Glads. You could even forego the Demo title in this scenario if you're feeling froggy. I've also played with the idea of a pile of bombers filling this role. You could try to extract value from Konnie by not having to activate the bombers, since you could tarpit the prey and keep them in range until dead, but then you're still looking at the squadron points spent on fighters, and they really would need to be "kill the other guy's squadrons" fighters rather than a defensive escort, so you lose some efficiency there too.
So, put it all together, and I like the idea of a pair of very lightly-loaded QFs in the wings, pushing your fighter defense screen, and then a few Raiders or a couple of GSDs in your backfield as the catchers. I lean toward the Raiders because, when you're throwing two fairly-vulnerable QFs out front of the fleet, you really want activations to minimize the shots they're eating. I'm not sure exactly how I would build this out, as points get tight fast when you're buying two QFs for a flanking role, but it's at least a framework for approaching Konstantine listbuilding.
The biggest issue is how in the world can you recapture enough value with your exploiters to justify a 108-point minimum investment on those QFs. Bearing in mind that you could instead just buy an ISD1 with those points and use a different admiral. ISDs are really good at splitting up fleets too: by shooting the other half .
Don't know if I like that though... Hmm...